Question

1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

中文文档

Description

You are given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

• arr has exactly n integers.
• 1 <= arr[i] <= m where (0 <= i < n).
• After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return _the number of ways_ to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 109 + 7.

 

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

 

Constraints:

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

Solutions

Solution 1

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
}