Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1155.html

1155. Number of Dice Rolls With Target Sum (Medium)

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

 

Example 1:

Input: d = 1, f = 6, target = 3
Output: 1
Explanation: 
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2:

Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:

Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:

Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

 

Constraints:

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

Related Topics:
Dynamic Programming

Solution 1. DP Top-down

Let dp[i][t] be the number of dice rolls with i dices and t target sum.

dp[i][t] = sum( dp[i-1][t-j] | 1 <= j <= f )

dp[i][t] = 0 if t < d || t > d * f

dp[1][t] = 1 if 1 <= t <= f
// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DFT)
// Space: O(DT)
class Solution {
    vector<unordered_map<int, int>> m;
    long mod = 1e9+7;
    int dfs(int d, int f, int target) {
        if (target < d || target > d * f) return 0;
        if (d == 1) return 1; 
        if (m[d].count(target)) return m[d][target];
        long cnt = 0;
        for (int j = 1; j <= f && j <= target; ++j) {
            int c = dfs(d - 1, f, target - j);
            cnt = (cnt + c) % mod;
        }
        return m[d][target] = cnt;
    }
public:
    int numRollsToTarget(int d, int f, int target) {
        m.assign(d + 1, {});
        return dfs(d, f, target);
    }
};

Solution 2. DP Top-down with Optimization

dp[i][t] = sum( dp[i-1][t-j] | 1 <= j <= f )

dp[i][t] = dp[i-1][t-1] + dp[i-1][t-2] + ... + dp[i-1][t-f]
dp[i][t-1] =              dp[i-1][t-2] + ... + dp[i-1][t-f] + dp[i-1][t-f-1]

dp[i][t] = dp[i][t-1] + dp[i-1][t-1] - dp[i-1][t-f-1]
// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
    vector<unordered_map<int, int>> m;
    long mod = 1e9+7, f;
    int dfs(int d, int target) {
        if (target < d || target > d * f) return 0;
        if (d == 1) return 1; 
        if (m[d].count(target)) return m[d][target];
        return m[d][target] = (((long)dfs(d, target - 1) + dfs(d - 1, target - 1)) % mod - dfs(d - 1, target - f - 1) + mod) % mod;
    }
public:
    int numRollsToTarget(int d, int f, int target) {
        m.assign(d + 1, {});
        this->f = f;
        return dfs(d, target);
    }
};

Using array is always more time efficient.

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
    int m[31][1001] = {};
    long mod = 1e9+7, f;
    int dfs(int d, int target) {
        if (target < d || target > d * f) return 0;
        if (d == 1) return 1; 
        if (m[d][target] != -1) return m[d][target];
        return m[d][target] = (((long)dfs(d, target - 1) + dfs(d - 1, target - 1)) % mod - dfs(d - 1, target - f - 1) + mod) % mod;
    }
public:
    int numRollsToTarget(int d, int f, int target) {
        memset(m, -1, sizeof(m));
        this->f = f;
        return dfs(d, target);
    }
};

Solution 3. DP Bottom-up

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DTF)
// Space: O(DT)
class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        long dp[31][1001] = {}, mod = 1e9+7;
        for (int j = 1; j <= f; ++j) dp[1][j] = 1;
        for (int i = 2; i <= d; ++i) {
            for (int t = i; t <= target && t <= i * f; ++t) {
                for (int j = 1; j <= f && j < t; ++j) {
                    dp[i][t] = (dp[i][t] + dp[i - 1][t - j]) % mod;
                }
            }
        }
        return dp[d][target];
    }
};

Solution 4. DP Bottom-up with Optimization

// OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
// Time: O(DT)
// Space: O(DT)
class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        long dp[31][1001] = {}, mod = 1e9+7;
        for (int j = 1; j <= f; ++j) dp[1][j] = 1;
        for (int i = 2; i <= d; ++i) {
            for (int t = i; t <= target && t <= i * f; ++t) {
                dp[i][t] = (dp[i][t - 1] + dp[i - 1][t - 1]) % mod;
                if (t - f - 1 > 0) dp[i][t] = (dp[i][t] - dp[i - 1][t - f - 1] + mod) % mod;
            }
        }
        return dp[d][target];
    }
};
  • class Solution {
        public int numRollsToTarget(int d, int f, int target) {
            int min = d, max = d * f;
            if (target < min || target > max)
                return 0;
            if (d == 1 || target == min || target == max)
                return 1;
            final int MODULO = 1000000007;
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 1; i <= d; i++) {
                for (int j = target; j >= 0; j--) {
                    dp[j] = 0;
                    int upper = Math.min(f, j);
                    for (int k = 1; k <= upper; k++)
                        dp[j] = (dp[j] + dp[j - k]) % MODULO;
                }
            }
            return dp[target];
        }
    }
    
    ############
    
    class Solution {
        private static final int MOD = (int) 1e9 + 7;
    
        public int numRollsToTarget(int n, int k, int target) {
            int[][] f = new int[n + 1][target + 1];
            f[0][0] = 1;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= Math.min(target, i * k); ++j) {
                    for (int h = 1; h <= Math.min(j, k); ++h) {
                        f[i][j] = (f[i][j] + f[i - 1][j - h]) % MOD;
                    }
                }
            }
            return f[n][target];
        }
    }
    
  • // OJ: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
    // Time: O(DFT)
    // Space: O(DT)
    class Solution {
        vector<unordered_map<int, int>> m;
        long mod = 1e9+7;
        int dfs(int d, int f, int target) {
            if (target < d || target > d * f) return 0;
            if (d == 1) return 1; 
            if (m[d].count(target)) return m[d][target];
            long cnt = 0;
            for (int j = 1; j <= f && j <= target; ++j) {
                int c = dfs(d - 1, f, target - j);
                cnt = (cnt + c) % mod;
            }
            return m[d][target] = cnt;
        }
    public:
        int numRollsToTarget(int d, int f, int target) {
            m.assign(d + 1, {});
            return dfs(d, f, target);
        }
    };
    
  • class Solution:
        def numRollsToTarget(self, n: int, k: int, target: int) -> int:
            f = [[0] * (target + 1) for _ in range(n + 1)]
            f[0][0] = 1
            mod = 10**9 + 7
            for i in range(1, n + 1):
                for j in range(1, min(i * k, target) + 1):
                    for h in range(1, min(j, k) + 1):
                        f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod
            return f[n][target]
    
    ############
    
    # 1155. Number of Dice Rolls With Target Sum
    # https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
    
    class Solution:
        def numRollsToTarget(self, d: int, f: int, target: int) -> int:
            M = 10 ** 9 + 7
            
            @cache
            def dp(d, target):
                if d == 0: return 1 if target == 0 else 0
                
                count = 0
                for k in range(max(0, target - f), target):
                    count += dp(d - 1, k)
                
                return count
                
            return dp(d, target) % M
    
    
  • func numRollsToTarget(n int, k int, target int) int {
    	const mod int = 1e9 + 7
    	f := make([][]int, n+1)
    	for i := range f {
    		f[i] = make([]int, target+1)
    	}
    	f[0][0] = 1
    	for i := 1; i <= n; i++ {
    		for j := 1; j <= min(target, i*k); j++ {
    			for h := 1; h <= min(j, k); h++ {
    				f[i][j] = (f[i][j] + f[i-1][j-h]) % mod
    			}
    		}
    	}
    	return f[n][target]
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions