1155. Number of Dice Rolls With Target Sum

,

DFS

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
29
30
31
32
33
34
35
36
class Solution {
    private static final int MOD = 1000000007;

    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0;
        }

        int[][] cache = new int[n + 1][target + 1];
        for (int[] c : cache) {
            Arrays.fill(c, -1);
        }

        return dfs(cache, n, k, target);
    }

    private int dfs(int[][] cache, int n, int k, int target) {
        if (target < 0) {
            return 0;
        }

        if (n == 0) {
            return target == 0 ? 1 : 0;
        }

        if (cache[n][target] != -1) {
            return cache[n][target];
        }

        int count = 0;
        for (int i = 1; i <= k; i++) { // 枚举当前骰子可能摇出的值
            count = (count + dfs(cache, n - 1, k, target - i)) % MOD; // 注意此处先累加再取模，保证了 dfs 方法返回值始终小于 MOD，以避免越界
        }
        return cache[n][target] = count;
    }
}

自顶向下。

DP

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 {
    private static final int MOD = 1000000007;
    
    public int numRollsToTarget(int n, int k, int target) {
        // n 个骰子，每个骰子 k 个面，求和为 target 的方法数

        if (target < n || target > n * k) {
            return 0;
        }

        // 定义 dp[i][j] 为使用 i 个骰子时，和为 j 的方法数
        int[][] dp = new int[n + 1][target + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                for (int l = 1; l <= k; l++) {
                    if (j - l >= 0) {
                        dp[i][j] += dp[i - 1][j - l];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }

        return dp[n][target];
    }
}

自底向上。

References

1155. Number of Dice Rolls With Target Sum