本文主要是介绍leetcode_1155 掷骰子等于目标和的方法数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题意
n个k面的骰子，投掷出骰子的点数之和为target的所有可能。
掷骰子等于目标和的方法数
2. 题解
动态规划，实际上相当于一个0-1背包。
令 d p [ i ] [ j ] dp[i][j] dp[i][j]为前 i i i个骰子和为j的方案数
则
d p [ i ] [ j ] = ∑ t = 1 k d p [ i − 1 ] [ j − t ] , j ≤ t dp[i][j] = \sum_{t=1}^{k}dp[i - 1][j -t], j \le t dp[i][j]=t=1∑kdp[i−1][j−t],j≤t
- 代码
class Solution {
public:int numRollsToTarget(int n, int k, int target) {// dp[i][j] = dp[i - 1][j - k] j - k >= i - 1int dp[30 + 1][1000 + 1];memset(dp, 0, sizeof(dp));int MOD = 1e9 + 7;dp[0][0] = 1;for (int i = 1;i <= n; ++i)for (int j = i + 1; j <= min(k * i, target); ++j) {for (int inc = 1; inc <= k; ++inc ) {if ( i - 1 <= j - inc )dp[i][j] = (dp[i][j] + dp[i - 1][j - inc] )% MOD;}}return dp[n][target];}
};
这篇关于leetcode_1155 掷骰子等于目标和的方法数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
