Hard

题目描述

给你三个整数 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

解题思路

这是一道经典的动态规划问题。关键是理解 search_cost 的含义：它表示遍历数组时找到新的最大值的次数。

思路分析

我们需要定义状态：dp[i][j][cost] 表示前 i 个位置，当前最大值为 j，已经产生了 cost 次比较的方案数。

状态转移分两种情况：

  1. 不产生新的比较：当前位置填入 ≤ j 的数，最大值不变，比较次数不增加
  2. 产生新的比较：当前位置填入 > j 的数，最大值更新，比较次数增加 1

具体转移方程：

  • 情况1：dp[i][j][cost] += dp[i-1][j][cost] * j（有 j 种选择：1 到 j）
  • 情况2：dp[i][val][cost] += dp[i-1][j][cost-1]（val > j，从 j+1 到 m）

边界条件：dp[1][j][1] = 1（第一个位置填 j，产生 1 次比较）

最终答案：sum(dp[n][j][k]) for all j from 1 to m

时间复杂度 O(nm²k)，空间复杂度可以优化到 O(m*k)。

代码实现

class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        const int MOD = 1000000007;
        
        // dp[j][cost] = number of ways with max value j and cost comparisons
        vector<vector<long long>> dp(m + 1, vector<long long>(k + 1, 0));
        vector<vector<long long>> new_dp(m + 1, vector<long long>(k + 1, 0));
        
        // Base case: first position
        for (int j = 1; j <= m; j++) {
            dp[j][1] = 1;
        }
        
        // Fill for positions 2 to n
        for (int i = 2; i <= n; i++) {
            // Reset new_dp
            for (int j = 1; j <= m; j++) {
                for (int cost = 0; cost <= k; cost++) {
                    new_dp[j][cost] = 0;
                }
            }
            
            for (int j = 1; j <= m; j++) {
                for (int cost = 0; cost <= k; cost++) {
                    // Case 1: no new comparison (choose value <= j)
                    new_dp[j][cost] = (new_dp[j][cost] + dp[j][cost] * j) % MOD;
                    
                    // Case 2: new comparison (choose value j, previous max < j)
                    if (cost > 0) {
                        for (int prev_max = 1; prev_max < j; prev_max++) {
                            new_dp[j][cost] = (new_dp[j][cost] + dp[prev_max][cost - 1]) % MOD;
                        }
                    }
                }
            }
            
            dp = new_dp;
        }
        
        long long result = 0;
        for (int j = 1; j <= m; j++) {
            result = (result + dp[j][k]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        
        # dp[j][cost] = number of ways with max value j and cost comparisons
        dp = [[0] * (k + 1) for _ in range(m + 1)]
        
        # Base case: first position
        for j in range(1, m + 1):
            dp[j][1] = 1
        
        # Fill for positions 2 to n
        for i in range(2, n + 1):
            new_dp = [[0] * (k + 1) for _ in range(m + 1)]
            
            for j in range(1, m + 1):
                for cost in range(k + 1):
                    # Case 1: no new comparison (choose value <= j)
                    new_dp[j][cost] = (new_dp[j][cost] + dp[j][cost] * j) % MOD
                    
                    # Case 2: new comparison (choose value j, previous max < j)
                    if cost > 0:
                        for prev_max in range(1, j):
                            new_dp[j][cost] = (new_dp[j][cost] + dp[prev_max][cost - 1]) % MOD
            
            dp = new_dp
        
        return sum(dp[j][k] for j in range(1, m + 1)) % MOD

public class Solution {
    public int NumOfArrays(int n, int m, int k) {
        const int MOD = 1000000007;
        
        // dp[j][cost] = number of ways with max value j and cost comparisons
        long[,] dp = new long[m + 1, k + 1];
        
        // Base case: first position
        for (int j = 1; j <= m; j++) {
            dp[j, 1] = 1;
        }
        
        // Fill for positions 2 to n
        for (int i = 2; i <= n; i++) {
            long[,] newDp = new long[m + 1, k + 1];
            
            for (int j = 1; j <= m; j++) {
                for (int cost = 0; cost <= k; cost++) {
                    // Case 1: no new comparison (choose value <= j)
                    newDp[j, cost] = (newDp[j, cost] + dp[j, cost] * j) % MOD;
                    
                    // Case 2: new comparison (choose value j, previous max < j)
                    if (cost > 0) {
                        for (int prevMax = 1; prevMax < j; prevMax++) {
                            newDp[j, cost] = (newDp[j, cost] + dp[prevMax, cost - 1]) % MOD;
                        }
                    }
                }
            }
            
            dp = newDp;
        }
        
        long result = 0;
        for (int j = 1; j <= m; j++) {
            result = (result + dp[j, k]) % MOD;
        }
        
        return (int)result;
    }
}

var numOfArrays = function(n, m, k) {
    const MOD = 1000000007;
    
    // dp[j][cost] = number of ways with max value j and cost comparisons
    let dp = Array(m + 1).fill().map(() => Array(k + 1).fill(0));
    
    // Base case: first position
    for (let j = 1; j <= m; j++) {
        dp[j][1] = 1;
    }
    
    // Fill for positions 2 to n
    for (let i = 2; i <= n; i++) {
        let newDp = Array(m + 1).fill().map(() => Array(k + 1).fill(0));
        
        for (let j = 1; j <= m; j++) {
            for (let cost = 0; cost <= k; cost++) {
                // Case 1: no new comparison (choose value <= j)
                newDp[j][cost] = (newDp[j][cost] + dp[j][cost] * j) % MOD;
                
                // Case 2: new comparison (choose value j, previous max < j)
                if (cost > 0) {
                    for (let prevMax = 1; prevMax < j; prevMax++) {
                        newDp[j][cost] = (newDp[j][cost] + dp[prevMax][cost - 1]) % MOD;
                    }
                }
            }
        }
        
        dp = newDp;
    }
    
    let result = 0;
    for (let j = 1; j <= m; j++) {
        result = (result + dp[j][k]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m² × k)
空间复杂度O(m × k)