1155. 掷骰子的N种方法

这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, …, f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。

示例 1：

输入：d = 1, f = 6, target = 3
输出：1
示例 2：

输入：d = 2, f = 6, target = 7
输出：6
示例 3：

输入：d = 2, f = 5, target = 10
输出：1
示例 4：

输入：d = 1, f = 2, target = 3
输出：0
示例 5：

输入：d = 30, f = 30, target = 500
输出：222616187

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    int dp[31][1001];
    int mod = pow(10,9)+7;
public:
    int numRollsToTarget(int d, int f, int target) {
        if(target<d || target>d*f) return 0;
        for(int i = 1; i <= f; ++i){
            dp[1][i] = 1;
        }
        for(int i = 2; i <= d; ++i){
            for(int k = 1; k <= f; ++k){
                for(int j = 1; j <= f*d; ++j){
                    if(j<k) continue;
                    dp[i][j] = (dp[i][j]+dp[i-1][j-k])%mod;
                }
            }
        }

        return dp[d][target]%mod;
    }
};

class Solution {
    int dp[35][1050];//计算结果
    int vis[35][1050];//标记是否已经进行了计算
    int F;
    int mod = 1e9+7;

public:
    int DFS(int d,int tar){ //第d次选择，剩余tar
        if(d>tar) return 0;
        if(d ==0){
            if(tar == 0) return 1;
            else return 0;
        }
        if(vis[d][tar]>0) return dp[d][tar]; //如果已经进行了计算，就返回结果
        int ans = 0;
        for(int i =1;i<=F && i<=tar;i++){
            ans+=DFS(d-1,tar-i); //
            ans%=mod;
        }
        vis[d][tar] = 1;//已经算出了结果，做一个标记
        return dp[d][tar] = ans;//记忆化
    }


    int numRollsToTarget(int d, int f, int target) {
        F = f;
        return DFS(d,target);
    }
};