Dice throw

JavaView on GFG

Intuition

Count ways to get sum S with N dice, each having M faces. DP: dp[i][j] = ways to get sum j with i dice.

Algorithm

1dp[0][0] = 1.
2For each die d from 1 to N: for each sum j: dp[d][j] = sum of dp[d-1][j-f] for f in 1..min(m,j).
3Return dp[N][S].

Example Walkthrough

Input: N=2, M=6, S=4

1.dp[1] = [0,1,1,1,1,1,1]. dp[2][4] = dp[1][3]+dp[1][2]+dp[1][1] = 3.

Output: 3

Common Pitfalls

•1D DP with offset or 2D is clearer. Inner loop runs 1..min(m,j) to avoid going negative.

Dice throw.java

Java

// Approach: DP. dp[i][j] = ways to get sum j using i dice.
// Transition: dp[i][j] = sum of dp[i-1][j-face] for face in [1, m].
// Time: O(m * n * sum) Space: O(n * sum)
class Solution {
    static int noOfWays(int m, int n, int x) {
        if (n * m < x)
            return 0;

        int dp[][] = new int[n + 1][x + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= x; j++)
                dp[i][j] = -1;
        }

        return solve(m, n, x, dp);
    }

    static int solve(int m, int n, int x, int dp[][]) {
        if (n == 0 && x == 0)
            return 1;

        if (n == 0)
            return 0;

        if (dp[n][x] != -1)
            return dp[n][x];

        int ans = 0;
        for (int j = 1; j <= m; j++) {
            if (x - j >= 0)
                ans += solve(m, n - 1, x - j, dp);
        }

        return dp[n][x] = ans;
    }
};

Was this solution helpful?