1155. Number of Dice Rolls With Target Sum

time: O(d*target*f)

space: O(d*target*f)

/*
    3 dice, face = 6, target = 10 
    dp(3,6,10)
    
    use last dice, dice = 1, dp(2, 6, 9)
    use last dice, dice = 2, dp(2, 6, 8)
    use last dice, dice = 3, dp(2, 6, 7)
    use last dice, dice = 4, dp(2, 6, 6)
    use last dice, dice = 5, dp(2, 6, 5)
    use last dice, dice = 6, dp(2, 6, 4)
    
    so
    for (int i = 1; k <= f) {
        dp[dice][target] += dp[dice-1][target-k];
    }
*/
class Solution {
    public int numRollsToTarget(int d, int f, int target) {
        int mod = 1_000_000_007;
        long dp[][] = new long[d+1][target+1];
        
        dp[0][0] = 1; // exist one way for nothing
        for (int i = 1; i <= d; i++) {
            for (int j = 0; j <= target; j++) {
                for (int k = 1; k <= f; k++) {
                    if (j >= k) {
                        dp[i][j] = (dp[i][j] + dp[i-1][j-k])%mod;
                    }
                }
            }
        }
        return (int)dp[d][target]%mod;
    }
}

DFS + memo

```java
class Solution {
    private static final int MOD = 1000000007;

    private int solve(int d, int f, int target, Integer[][] dp) {
        if (d == 0 && target == 0) {
            return 1;
        }
        if (d == 0 || target == 0) {
            return 0;
        }
        if (dp[d][target] != null) { 
            return dp[d][target];
        }

        int sum = 0;
        for (int i = 1; i <= f; i++) {
            if (target - i < 0) {
                break;
            }
            sum = (sum % MOD + solve(d - 1, f, target - i, dp) % MOD) % MOD;
        }
        dp[d][target] = sum;
        return dp[d][target];
    }

    public int numRollsToTarget(int d, int f, int target) {
        Integer[][] dp = new Integer[d+1][target+1];
        return solve(d, f, target, dp);
    }
    
}
/**
T: O(n*target)
S: O(n*target)

 */
```