Leetcode:No.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

提示：
  • 1 <= d, f <=30
  • 1 <= target <=1000

解题思路

看似是投N个骰子，其实我们把过程细分一下会发现，投第1个骰子的点数X只有可能为[1,min(f,target)]，而且另外N-1个骰子的点数和为target-X,乍看很容易写出递归来。

递归方法(C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    const int mod=1E+09+7;
    int numRollsToTarget(int d, int f, int target) {
        if(d*f<target||d>target) return 0;
        if(d==1)
            return f>=target?1:0;
        int ans=0;
        int N=min(target-d+1,f);//一个骰子能取的最大值
        for(int i=1;i<=N;i++){
            ans+=numRollsToTarget(d-1,f,target-i)%mod;
        }
        return ans;
    }
};

但是经历告诉我，递归执行示例5这个测试时会超时。。。有兴趣的可以求下递归的时间复杂度
那么有没有别的办法呢？
当然有！那就是有点穷举意味的动态规划了！
步骤如下：

1.比如此题dp[i][j]表示的是掷i个骰子和为j，其值为方法数。
2.接着便是此法的关键——列出状态转移方程(STE)：
dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+...+dp[i-1][j-N]; 其中N=min(f,j-1);
3.之后给定迭代的初始值
4.把STE用代码实现
DP(C++)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numRollsToTarget(int d, int f, int target) {
        const int mod=1E+09+7;
        int dp[31][1001]={0};//dp[i][j]，投i个骰子和为j的方法数
        int N=min(f,target);
        for(int i=1;i<=N;i++){
            dp[1][i]=1;
        }
        int targetmax=min(d*f,target);
        for(int i=2;i<=d;i++)
            for(int j=i;j<=targetmax;j++){
                for(int k=1;k<=min(j-i+1,f);k++){//k表示第i个骰子能取的点数
                    dp[i][j]=(dp[i][j]+dp[i-1][j-k])%mod;
                }
            }
        return dp[d][target];
    }
};

以上就是我的第一个post，感谢大家百忙中抽出时间阅读！有什么疑惑可以在下面留言哦~