Welcome back to our daily leetcode problem, Day 26. I hope that you all had a pleasant Christmas.

Link Problem

Solution to this problem:

• Using Dynamic Programming.

• Call dp[n][target] is a result for n dice and with current sum (or target).

• For every state, we will have k possible values, which is using 1 up to k to add to target.

• We can also see that, some states (n, target) is repeatedly calculated so we will store it array dp to avoid redundant.

TC: O(n × k x target)

Code:

class Solution {
private:
    const int mod = 1e9 + 7;
    int dp[1011][1011];
public:

    int ADD(int a) {
        if(a >= mod)
            a -= mod;
        return a;
    }

    int solve(int n, int k, int target) {
        if(n == 0) {
            return target == 0;
        }

        if(target <= 0) return 0;

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

        int ways = 0;

        for(int i = 1; i <= k; ++i) {
            ways = ADD((long)ways + solve(n - 1, k, target - i));
        }

        return dp[n][target] = ways;
    }

    int numRollsToTarget(int n, int k, int target) {
        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= target; ++j)
                dp[i][j] = -1;

        return solve(n, k, target);
    }
};