1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    // dp[n][m] = sum(dp[n - 1][m - 1] + dp[n - 1][m - 2] + ... + dp[n - 1][m - k]);
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        int modulo = (int) 1e9 + 7;
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int value = 1; value <= k && j - value > 0; value++) {
                    dp[i][j] = Math.floorMod(dp[i][j] + dp[i - 1][j - value], modulo);
                }
            }
        }
        return dp[n][target];
    }
}

如果最后一个骰子是1, 那我知道之前n - 1个骰子凑target - 1的种类个数就好了; 如果最后一个骰子是2, 那我知道之前n - 1个骰子凑target - 2的种类个数就好了… 一次类推. dp[n][m] = sum(dp[n - 1][m - 1] + dp[n - 1][m - 2] + … + dp[n - 1][m - k])

需要注意的是, dp[0][0]的值是1, 因为如果按照我们的逻辑dp[1][1]就要看dp[0][0]是多少, 我们知道1个骰子凑1肯定只有一种, 因此为了满足我们的逻辑dp[0][0] == 1. 但是之后的每行第0个位置就是0, 因为当骰子数目大于等于1的时候, 是无法凑成0的.

时间复杂度: O(n * target * k)
空间复杂度: O(n * target)