leetcode 1420

问题

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

img

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 10^9 + 7.

Example 1:

1
2
3
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:

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

Example 3:

1
2
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]

Example 4:

1
2
3
Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

1
2
Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

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

分析

dp[i][j][k] 表示数组长度为 $i$ ，其中最大的元素是 $j$ ，并且经过 $k$ 的 search_cost。

我们以数组长度 $i$ 为dp的阶段，那么 dp[i][j][k] 可以划分为两类子问题。

  1. dp[i][j][k] = j* dp[i-1][j][k] ，如果现在有一个长度为 i-1 的数组，其最大的元素是 j ，并且经过 search_cost = k 找到它。那么我们经过这个数组得到一个长度为 i 的数组就可以在其最后一位添加 1-j 中任意一位数组。（第一个最大元素j不是在数组的最后一位找到的）
  2. dp[i][j][k] = SUM (from x = 1 to x = j-1) dp[i-1][x][k-1] （第一个最大元素j是在数组的最后一位找到的）

则目标就是 SUM from j = 1 to j = m dp[n][j][k]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    
    int numOfArrays(int n, int m, int k) {
        if (k == 0) return 0;
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(m+1, vector<int>(k+1, 0)));
        for (int j = 1; j <= m; ++j) {
            dp[1][j][1] = 1;
        }
        
        for (int a = 2; a <= n; ++a) {
            for (int b = 1; b <= m; ++b) {
                for (int c = 1; c <= k; ++c) {
                    long long t = (long long)dp[a-1][b][c]*b;
                    for (int i = 1; i < b; ++i) {
                        t += dp[a-1][i][c-1];
                    }
                    dp[a][b][c] = t%1000000007;
                }
            }
        }
        long long ans = 0;
        for (int j = 1; j <= m; ++j) {
            ans += dp[n][j][k];
        }
        return ans%1000000007;
    }
};