列表

详情

1420. 生成数组

给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。

请你生成一个具有下述属性的数组 arr ：

返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

 

示例 1：

输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

示例 2：

输入：n = 5, m = 2, k = 3
输出：0
解释：没有数组可以满足上述条件

示例 3：

输入：n = 9, m = 1, k = 1
输出：1
解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]

示例 4：

输入：n = 50, m = 100, k = 25
输出：34549172
解释：不要忘了对 1000000007 取余

示例 5：

输入：n = 37, m = 17, k = 7
输出：418930126

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int numOfArrays(int n, int m, int k) { } };

golang 解法, 执行用时: 48 ms, 内存消耗: 4.2 MB, 提交时间: 2023-06-15 14:32:32 

const mod int64 = 1000000007
func numOfArrays(n int, m int, w int) int {
	if w==0{
		return 0;
	}
    var dp [55][105][55]int64  // 数组的第i位 最大值是j且比较次数是k 的方法数
	for i:=1;i<=m;i++{
		dp[1][i][1]=1;
	}
	for i:=2;i<=n;i++{
		for j:=1;j<=m;j++{
			for k:=1;k<=w;k++{
				for l:=1;l<j;l++{
					dp[i][j][k]+=dp[i-1][l][k-1]
					dp[i][j][k]%=mod
				}
				dp[i][j][k]+=dp[i-1][j][k]*(int64(j))%mod
				dp[i][j][k]%=mod
			}
		}
	}
	var ans int64 =0
	for i:=1;i<=m;i++{
		ans+=dp[n][i][w]
		ans%=mod
	}
	return (int)(ans)
}

golang 解法, 执行用时: 12 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-15 14:31:27 

func numOfArrays(n int, m int, k int) int {
	if k > m {
		return 0
	}

	M := int(1e9) + 7
	dp := make([][][]int, n)  // i 当前位置, j 当前max值, k 剩余cost
	sum := make([][][]int, n)  // dp[j]前缀和
	for i := 0; i < n; i++ {
		dp[i] = make([][]int, m)
		sum[i] = make([][]int, m)
		for j := 0; j < m; j++ {
			dp[i][j] = make([]int, k)
			sum[i][j] = make([]int, k)
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ { // 选出作为max
			if i == 0 {
				dp[0][j][k-1] = 1
				sum[0][j][k-1] = j + 1
				continue
			}

			for x := 0; x < k; x++ {
				dp[i][j][x] = dp[i-1][j][x] * (j+1) // 之前的max比j大
				if j > 0 && x+1 < k {
					dp[i][j][x] += sum[i-1][j-1][x+1] // 之前max比j小，则：max=j  x--
				}
				dp[i][j][x] %= M

				sum[i][j][x] = dp[i][j][x]
				if j > 0 {
					sum[i][j][x] += sum[i][j-1][x]
				}
				sum[i][j][x] %= M
			}
		}
	}

	return sum[n-1][m-1][0]
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.9 MB, 提交时间: 2023-06-15 14:30:17 

class Solution {
private:
    int f[51][51][101];
    static constexpr int mod = 1000000007;

public:
    int numOfArrays(int n, int m, int k) {
        // 不存在搜索代价为 0 的数组
        if (!k) {
            return 0;
        }
        
        memset(f, 0, sizeof(f));
        // 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for (int j = 1; j <= m; ++j) {
            f[1][1][j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            // 搜索代价不会超过数组长度
            for (int s = 1; s <= k && s <= i; ++s) {
                // 前缀和
                int presum_j = 0;
                for (int j = 1; j <= m; ++j) {
                    f[i][s][j] = (long long)f[i - 1][s][j] * j % mod;
                    f[i][s][j] = (f[i][s][j] + presum_j) % mod;
                    presum_j = (presum_j + f[i - 1][s - 1][j]) % mod;
                }
            }
        }

        // 最终的答案是所有 f[n][k][..] 的和
        // 即数组长度为 n，搜索代价为 k，最大值任意
        int ans = 0;
        for (int j = 1; j <= m; ++j) {
            ans += f[n][k][j];
            ans %= mod;
        }
        return ans;
    }
};

python3 解法, 执行用时: 100 ms, 内存消耗: 19.8 MB, 提交时间: 2023-06-15 14:30:04 

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        # 不存在搜索代价为 0 的数组
        if k == 0:
            return 0

        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]
        mod = 10**9 + 7
        # 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for j in range(1, m + 1):
            f[1][1][j] = 1
        for i in range(2, n + 1):
            # 搜索代价不会超过数组长度
            for s in range(1, min(k, i) + 1):
                # 前缀和
                presum_j = 0
                for j in range(1, m + 1):
                    f[i][s][j] = (f[i - 1][s][j] * j + presum_j) % mod
                    presum_j += f[i - 1][s - 1][j]
        
        # 最终的答案是所有 f[n][k][..] 的和
        # 即数组长度为 n，搜索代价为 k，最大值任意
        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod
        return ans

java 解法, 执行用时: 10 ms, 内存消耗: 42.5 MB, 提交时间: 2023-06-15 14:29:51 

class Solution {
    int[][][] f = new int[51][51][101];
    final int MOD = 1000000007;

    public int numOfArrays(int n, int m, int k) {
        // 不存在搜索代价为 0 的数组
        if (k == 0) {
            return 0;
        }
        
        // 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for (int j = 1; j <= m; ++j) {
            f[1][1][j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            // 搜索代价不会超过数组长度
            for (int s = 1; s <= k && s <= i; ++s) {
                // 前缀和
                int presum_j = 0;
                for (int j = 1; j <= m; ++j) {
                    f[i][s][j] = (int) ((long)f[i - 1][s][j] * j % MOD);
                    f[i][s][j] = (f[i][s][j] + presum_j) % MOD;
                    presum_j = (presum_j + f[i - 1][s - 1][j]) % MOD;
                }
            }
        }

        // 最终的答案是所有 f[n][k][..] 的和
        // 即数组长度为 n，搜索代价为 k，最大值任意
        int ans = 0;
        for (int j = 1; j <= m; ++j) {
            ans += f[n][k][j];
            ans %= MOD;
        }
        return ans;
    }
}

java 解法, 执行用时: 57 ms, 内存消耗: 42.5 MB, 提交时间: 2023-06-15 14:29:26 

class Solution {
    int[][][] f = new int[51][51][101];
    final int MOD = 1000000007;

    public int numOfArrays(int n, int m, int k) {
        // 不存在搜索代价为 0 的数组
        if (k == 0) {
            return 0;
        }
        
        // 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for (int j = 1; j <= m; j++) {
            f[1][1][j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            // 搜索代价不会超过数组长度
            for (int s = 1; s <= k && s <= i; ++s) {
                for (int j = 1; j <= m; ++j) {
                    f[i][s][j] = (int) ((long) f[i - 1][s][j] * j % MOD);
                    for (int j0 = 1; j0 < j; ++j0) {
                        f[i][s][j] += f[i - 1][s - 1][j0];
                        f[i][s][j] %= MOD;
                    }
                }
            }
        }

        // 最终的答案是所有 f[n][k][..] 的和
        // 即数组长度为 n，搜索代价为 k，最大值任意
        int ans = 0;
        for (int j = 1; j <= m; ++j) {
            ans += f[n][k][j];
            ans %= MOD;
        }
        return ans;
    }
}

python3 解法, 执行用时: 964 ms, 内存消耗: 19.6 MB, 提交时间: 2023-06-15 14:29:09 

# f[i][s][j] 表示长度为 i，搜索代价为 s，最大值为 j 的数组的数量。
class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        # 不存在搜索代价为 0 的数组
        if k == 0:
            return 0

        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]
        mod = 10**9 + 7
        # 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for j in range(1, m + 1):
            f[1][1][j] = 1
        for i in range(2, n + 1):
            # 搜索代价不会超过数组长度
            for s in range(1, min(k, i) + 1):
                for j in range(1, m + 1):
                    f[i][s][j] = f[i - 1][s][j] * j
                    for j0 in range(1, j):
                        f[i][s][j] += f[i - 1][s - 1][j0]
                    f[i][s][j] %= mod
        
        # 最终的答案是所有 f[n][k][..] 的和
        # 即数组长度为 n，搜索代价为 k，最大值任意
        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod
        return ans

cpp 解法, 执行用时: 32 ms, 内存消耗: 6.9 MB, 提交时间: 2023-06-15 14:28:41 

class Solution {
private:
    int f[51][51][101];
    static constexpr int mod = 1000000007;

public:
    int numOfArrays(int n, int m, int k) {
        // 不存在搜索代价为 0 的数组
        if (!k) {
            return 0;
        }
        
        memset(f, 0, sizeof(f));
        // 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for (int j = 1; j <= m; ++j) {
            f[1][1][j] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            // 搜索代价不会超过数组长度
            for (int s = 1; s <= k && s <= i; ++s) {
                for (int j = 1; j <= m; ++j) {
                    f[i][s][j] = (long long)f[i - 1][s][j] * j % mod;
                    for (int j0 = 1; j0 < j; ++j0) {
                        f[i][s][j] += f[i - 1][s - 1][j0];
                        f[i][s][j] %= mod;
                    }
                }
            }
        }

        // 最终的答案是所有 f[n][k][..] 的和
        // 即数组长度为 n，搜索代价为 k，最大值任意
        int ans = 0;
        for (int j = 1; j <= m; ++j) {
            ans += f[n][k][j];
            ans %= mod;
        }
        return ans;
    }
};

上一题

© 2024 leetcode.cn