LeetCode 1420. 生成数组

Categories:

题目描述
思路分析
1. 解法一：DP + 前缀和优化（推荐）
相似题目

题目描述

✅ 1420. 生成数组

思路分析

解法一：DP + 前缀和优化（推荐）

核心思路：

设 dp[j][c] 为长度到当前、最大值为 j、搜索代价为 c 的方案数。

追加新值 x：若 x <= j，代价不变；若 x = j，代价 +1。

用前缀和加速 sum_{p<j} dp[p][c-1]。

复杂度分析：

时间复杂度：O(n _ m _ k)。

空间复杂度：O(m * k)。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int numOfArrays(int n, int m, int k) {
        int[][] dp = new int[m + 1][k + 1];
        for (int j = 1; j <= m; j++) {
            dp[j][1] = 1;
        }

        for (int len = 2; len <= n; len++) {
            int[][] ndp = new int[m + 1][k + 1];
            int[][] prefix = new int[m + 1][k + 1];
            for (int j = 1; j <= m; j++) {
                for (int c = 1; c <= k; c++) {
                    prefix[j][c] = (prefix[j - 1][c] + dp[j][c]) % MOD;
                }
            }

            for (int j = 1; j <= m; j++) {
                for (int c = 1; c <= k; c++) {
                    long sameMax = (long) dp[j][c] * j % MOD;
                    long newMax = c > 1 ? prefix[j - 1][c - 1] : 0;
                    ndp[j][c] = (int) ((sameMax + newMax) % MOD);
                }
            }
            dp = ndp;
        }

        int ans = 0;
        for (int j = 1; j <= m; j++) {
            ans = (ans + dp[j][k]) % MOD;
        }
        return ans;
    }
}

func numOfArrays(n int, m int, k int) int {
    const mod = 1000000007
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, k+1)
    }
    for j := 1; j <= m; j++ {
        dp[j][1] = 1
    }

    for length := 2; length <= n; length++ {
        ndp := make([][]int, m+1)
        prefix := make([][]int, m+1)
        for i := 0; i <= m; i++ {
            ndp[i] = make([]int, k+1)
            prefix[i] = make([]int, k+1)
        }
        for j := 1; j <= m; j++ {
            for c := 1; c <= k; c++ {
                prefix[j][c] = prefix[j-1][c] + dp[j][c]
                if prefix[j][c] >= mod {
                    prefix[j][c] -= mod
                }
            }
        }

        for j := 1; j <= m; j++ {
            for c := 1; c <= k; c++ {
                sameMax := int64(dp[j][c]) * int64(j) % mod
                newMax := int64(0)
                if c > 1 {
                    newMax = int64(prefix[j-1][c-1])
                }
                ndp[j][c] = int((sameMax + newMax) % mod)
            }
        }
        dp = ndp
    }

    ans := 0
    for j := 1; j <= m; j++ {
        ans += dp[j][k]
        if ans >= mod {
            ans -= mod
        }
    }
    return ans
}

相似题目

题目	难度	考察点
1155. 掷骰子等于目标和的方法数	中等	DP
1335. 工作计划的最低难度	困难	DP
1746. 经过一次操作后的最大子数组和	中等	DP
1473. 粉刷房子 III	困难	DP
629. K 个逆序对数组	困难	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/98039080