LeetCode1155.掷骰子的N种方法（DP）Michael是个半路程序员-

1. 题目

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

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

如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有
$f^d$

fd 种），模 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 

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

2. 解题

类似题目：
剑指Offer – 面试题60. n个骰子的点数（动态规划）
LeetCode 1223. 掷骰子模拟（DP）

• 从上一次的所有状态推导当前次的状态

class Solution { // C++ public: int numRollsToTarget(int d, int f, int target) {      vector<vector<int>> dp(d+1,vector<int>(target+1, 0));      dp[0][0] = 1; int i,j,k; for(i = 1; i <= d; ++i) { for(j = 0; j < target; ++j) { if(dp[i-1][j] != 0)//上一次的状态存在 { for(k = 1; k <= f; ++k) { if(j+k <= target)//状态转移           dp[i][j+k] = (dp[i][j+k]+dp[i-1][j])%1000000007; } } } } return dp[d][target]; } }; 

36 ms 8.7 MB

python3 注意二维数组的写法

class Solution:# py3 def numRollsToTarget(self, d: int, f: int, target: int) -> int:         dp = [[0 for i in range(target+1)] for i in range(d+1)]         dp[0][0] = 1 for i in range(1,d+1): for j in range(0, target): if dp[i-1][j]==0: continue for k in range(1, f+1): if j+k <= target:                         dp[i][j+k] = (dp[i][j+k]+dp[i-1][j])%1000000007 return dp[d][target] 

524 ms 13.9 MB