Question

1420. 生成数组

English Version

题目描述

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

请你构建一个具有以下属性的数组 arr ：

• arr 中包含确切的 n 个整数。
• 1 <= arr[i] <= m 其中 (0 <= i < n) 。
• 将上面提到的算法应用于 arr 之后，search_cost 的值等于 k 。

返回在满足上述条件的情况下构建数组 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]

 

提示：

• 1 <= n <= 50
• 1 <= m <= 100
• 0 <= k <= n

解法

方法一：动态规划

假设 $dp[i][c][j]$ 表示长度为 $i$，搜索代价为 $c$，且最大值为 $j$ 的方案数。考虑第 $i$ 个数：

若第 $i$ 个数没有改变搜索代价，说明它不严格大于前 $i-1$ 个数，也就是说，$dp[i][c][j]$ 是从 $dp[i-1][c][j]$ 转移而来，即数组的前 $i-1$ 个数的最大值已经是 $j$，并且第 $i$ 个数没有改变最大值，因此第 $i$ 个数的可选范围是 $[1,..j]$，共有 $j$ 种可选方案。即

$$ dp[i][c][j]=dp[i-1][c][j] \times j $$

若第 $i$ 个数改变了搜索代价，说明数组前 $i-1$ 个数的最大值小于 $j$，并且第 $i$ 个数恰好为 $j$。此时 $dp[i][c][j]$ 是从所有 $dp[i-1][c-1][j']$ 转移而来，其中 $j'<j$。即

$$ dp[i][c][j] = \sum_{j'=1}^{j-1} dp[i-1][c-1][j'] $$

综上，可得

$$ dp[i][c][j] = dp[i-1][c][j] \times j + \sum_{j'=1}^{j-1} dp[i-1][c-1][j'] $$

答案为

$$ \sum_{j=1}^{m}dp[n][k][j] $$

时间复杂度 $O(nkm^2)$。

class Solution:
  def numOfArrays(self, n: int, m: int, k: int) -> int:
    if k == 0:
      return 0
    dp = [[[0] * (m + 1) for _ in range(k + 1)] for _ in range(n + 1)]
    mod = 10**9 + 7
    for i in range(1, m + 1):
      dp[1][1][i] = 1
    for i in range(2, n + 1):
      for c in range(1, min(k + 1, i + 1)):
        for j in range(1, m + 1):
          dp[i][c][j] = dp[i - 1][c][j] * j
          for j0 in range(1, j):
            dp[i][c][j] += dp[i - 1][c - 1][j0]
            dp[i][c][j] %= mod
    ans = 0
    for i in range(1, m + 1):
      ans += dp[n][k][i]
      ans %= mod
    return ans

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int numOfArrays(int n, int m, int k) {
    if (k == 0) {
      return 0;
    }
    long[][][] dp = new long[n + 1][k + 1][m + 1];
    for (int i = 1; i <= m; ++i) {
      dp[1][1][i] = 1;
    }
    for (int i = 2; i <= n; ++i) {
      for (int c = 1; c <= Math.min(i, k); ++c) {
        for (int j = 1; j <= m; ++j) {
          dp[i][c][j] = (dp[i - 1][c][j] * j) % MOD;
          for (int j0 = 1; j0 < j; ++j0) {
            dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % MOD;
          }
        }
      }
    }
    long ans = 0;
    for (int i = 1; i <= m; ++i) {
      ans = (ans + dp[n][k][i]) % MOD;
    }
    return (int) ans;
  }
}

class Solution {
public:
  int numOfArrays(int n, int m, int k) {
    if (k == 0) return 0;
    int mod = 1e9 + 7;
    using ll = long long;
    vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(k + 1, vector<ll>(m + 1)));
    for (int i = 1; i <= m; ++i) dp[1][1][i] = 1;
    for (int i = 2; i <= n; ++i) {
      for (int c = 1; c <= min(i, k); ++c) {
        for (int j = 1; j <= m; ++j) {
          dp[i][c][j] = (dp[i - 1][c][j] * j) % mod;
          for (int j0 = 1; j0 < j; ++j0) {
            dp[i][c][j] = (dp[i][c][j] + dp[i - 1][c - 1][j0]) % mod;
          }
        }
      }
    }
    ll ans = 0;
    for (int i = 1; i <= m; ++i) ans = (ans + dp[n][k][i]) % mod;
    return (int) ans;
  }
};

func numOfArrays(n int, m int, k int) int {
  if k == 0 {
    return 0
  }
  mod := int(1e9) + 7
  dp := make([][][]int, n+1)
  for i := range dp {
    dp[i] = make([][]int, k+1)
    for j := range dp[i] {
      dp[i][j] = make([]int, m+1)
    }
  }
  for i := 1; i <= m; i++ {
    dp[1][1][i] = 1
  }
  for i := 2; i <= n; i++ {
    for c := 1; c <= k && c <= i; c++ {
      for j := 1; j <= m; j++ {
        dp[i][c][j] = (dp[i-1][c][j] * j) % mod
        for j0 := 1; j0 < j; j0++ {
          dp[i][c][j] = (dp[i][c][j] + dp[i-1][c-1][j0]) % mod
        }
      }
    }
  }
  ans := 0
  for i := 1; i <= m; i++ {
    ans = (ans + dp[n][k][i]) % mod
  }
  return ans
}