Leetcode 2585. Number of Ways to Earn Points

[Woodyiiiiiii]

很经典的knapsack背包DP问题。

类似题目有：

• 322. Coin Change
• 518. Coin Change II
• 2518. Number of Great Partitions (相似/limited coin change)
• 2547. Minimum Cost to Split an Array

先确立coin。因为题目notes，比如[6,1]，因为题目说了跟1的次数有关，所以我们只关注1的数目就行了，{1,2,...6}。

又因为为了保证不被重复，对于dp[i]，一般要从后往前遍历，如果从前往后，就会被之前的影响。

难点是如何解决重复性问题。这就有关于内循环的变量顺序问题了。

首先最外层肯定是types，接着内层是i -> type[1]呢，还是type[1] -> i呢？如果是后者，那就比较麻烦，会出现重复计算的情况，比如先计算了[1,1]，等到计算[1,1,1]的时候，会把[1,1]计算的次数也包括进来，这样结果集中就出现了[1,1,1,1,1]的情况。

当然顺着这个思路硬着头皮做下去了，就是需要多命名些空间，将其分开来。

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        long[] dp = new long[target + 1];
        dp[0] = 1;
        final int MOD = 1000000007;
        for (int[] type : types) {
            int count = type[0];
            int marks = 0;
            long[] tmp = new long[target + 1];
            for (int i = 1; i <= count; ++i) {
                marks += type[1];
                long[] dp2 = new long[target + 1];
                System.arraycopy(dp, 0, dp2, 0, target + 1);
                for (int j = target; j >= marks; --j) {
                    if (dp2[j - marks] > 0) {
                        dp2[j] += dp2[j - marks];
                        dp2[j] %= MOD;
                    }
                }
//                System.out.println(".");
                for (int j = 1; j <= target; ++j) {
                    tmp[j] += dp2[j];
                    tmp[j] %= MOD;
                    tmp[j] = (tmp[j] - dp[j] + MOD) % MOD;
                }
//                System.out.println(Arrays.toString(tmp));
            }
            for (int j = 0; j <= target; ++j) {
                dp[j] += tmp[j];
                dp[j] %= MOD;
            }
        }
        return (int) dp[target];
    }
}

如果是前者，就好做多了。

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int[] dp = new int[target + 1];
        final int MOD = (int) (1e9 + 7);
        dp[0] = 1;
        for (int[] type : types) {
            for (int i = target; i >= 0; i--) {
                for (int k = type[1]; k <= type[0] * type[1] && i - k >= 0; k += type[1]) {
                    dp[i] = (dp[i] + dp[i - k]) % MOD;
                }
            }
        }
        return dp[target];
    }
}

此时对于i，i-type是没被计算过的。