1155. Number of Dice Rolls With Target Sum.md

1155. Number of Dice Rolls With Target Sum

思路

仔细分析一下可知，d个骰子的和为 target 的情况数取决于 d-1 个骰子的和为target-1、target-2...target-f的情况数。所以这题是一个典型的动态规划题。状态定义为

dp[i][j]: i个骰子的和为j的情况数，dp[0][0]=1

状态转移方程为：

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

思路一、自上而下

动态规划一般都可以转换成带记忆数组的递归，这题也不例外。

时间复杂度O(d * f * target)，空间复杂度O(d * target)

思路二、自下而上

更常见的是自下而上，而且我们还可以使用滚动数组对空间进行优化。

时间复杂度O(d * f * target)，空间复杂度O(target)

思路三

思路二一共有三层循环，可以进一步优化时间。

回顾一下状态转移方程，

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

j++后:
dp[i][j+1] = dp[i-1][j] + dp[i-1][j-1] +...+ dp[i-1][j-f+1]

所以说连续两次运行第三次循环是有大量重复的，所以第三层循环不是必须的。

可以这样考虑，dp[i][j] 的计算就是求一个大小为 f 的在数组dp[i-1]上的滑动窗口的元素和，思路二的第三层循环每次都从头到尾累加窗口内的元素，但事实上我们可以维护一个变量s代表窗口内元素的和，当窗口向右滑动一步时我们只需要将s加上窗口右端元素然后减去刚刚离开窗口左端的元素即可。

时间复杂度O(d * target)，空间复杂度O(target)

C++

思路一

class Solution {
private:
    vector<vector<int>>dp = vector<vector<int>>(31, vector<int>(1001, -1));
public:
    int numRollsToTarget(int d, int f, int target) {
        if(target < 0 || target > d * f) return 0;
        if(d == 0) return target == 0 ? 1 : 0;
        
        if(dp[d][target] >= 0) return dp[d][target];
        int res = 0;
        for(int i = 1; i <=f; i++){
            res += numRollsToTarget(d - 1, f, target - i);
            res %= 1000000007;
        }
        
        dp[d][target] = res;
        return res;
    }
};

思路二

class Solution {    
public:
    int numRollsToTarget(int d, int f, int target) {
        if(target > d * f) return 0; // 会大大减少测试时间

        vector<int>dp(target+1, 0);
        dp[0] = 1;
        for(int i = 1; i <= d; i++)
            for(int j = target; j >= 0; j--){ // 注意这里要反向遍历!
                int max_k = min(j, f); dp[j] = 0;
                for(int k = 1; k <= max_k; k++){
                    dp[j] += dp[j-k];
                    dp[j] %= 1000000007;
                }
            }
        return dp[target];
    }
};

思路三

class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        const int M = 1000000007;
        
        // dp表示dp[i][...], pre代表dp[i-1][...]
        vector<int> dp(target + 1, 0), pre(target + 1, 0);
        dp[0] = 1;
        long long s = 0;
        for(int i = 1; i <= d; i++){
            for(int t = 0; t <= target; t++) pre[t] = dp[t];
            
            s = 0;
            for(int j = 0; j <= target; j++){
                dp[j] = s;
                s += pre[j]; // 累加上窗口右端元素
                if(j >= f) s += M - pre[j - f]; // 减去刚刚离开窗口左端的元素
                s %= M;
            }
        } 
        return dp[target];
    }
};