leetcode第 149 场周赛 1155. 掷骰子的N种方法

超、凢脫俗 2021-11-01 04:44 269阅读 0赞

# [掷骰子的N种方法][N] #

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

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

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

1 < = d , f < = 30 1 <= d, f <= 30 1<=d,f<=30  
 1 < = t a r g e t < = 1000 1 <= target <= 1000 1<=target<=1000

示例 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

--------------------

动态规划，dp\[i\]\[j\]表示前i个骰子上面数字之和为j的种类数  
假设我第i次掷骰子得到的数字为k,那么dp\[i\]\[j\] += dp\[i-1\]\[j-k\]  
边界 dp\[1\]\[1->target\] = 1

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 2000;
    const int MOD  = 1e9+7;
    int dp[33][MAXN];
    /*
    dp[i][j]:=前i个筛子上面数字 之和为 j的种类数
    */
    
    int main() {
        
            int d,f,target;
            while(cin>>d>>f>>target) {
        
                    memset(dp,0,sizeof(dp));
                    for(int i=1;i<=f;++i)   dp[1][i] = 1;//
                    for(int i=1;i<=d;++i) {
         // 有d个骰子
                            for(int k=1;k<=f;++k){
         //每个骰子最大的数是f
                                    for(int j=1;j<=target;++j) {
        
                                            if(j>k) dp[i][j] += dp[i-1][j-k];
                                            dp[i][j] %= MOD;
                                    }
                            }
                    }
                    cout<<dp[d][target]<<endl;
            }
            return 0;
    }

[N]: https://leetcode-cn.com/contest/weekly-contest-149/problems/number-of-dice-rolls-with-target-sum/