掷骰子的N种方法
掷骰子的N种方法
题目：
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
答案可能很大，你需要对 109 + 7 取模 。
示例：
输入：n = 1, k = 6, target = 3 输出：1 解释：你扔一个有6张脸的骰子。 得到3的和只有一种方法。
思路：
投掷骰子的方法数：d个骰子,每个有f个面(点数为1,2,…f),求骰子点数和为target的方法
分组0/1背包的组合问题：dp[i][j]表示投掷i个骰子点数和为j的方法数;三层循环：最外层为背包d,然后先遍历target后遍历点数f
应用二维拓展的转移方程3：dp[i][j]+=dp[i-1][j-f];
代码：
Java版本：
class Solution { int mod = (int)1e9+7; public int numRollsToTarget(int n, int k, int t) { int[] dp = new int[t + 1]; dp[0] = 1; for(int i= 0 ; i < n ; i++){ for(int j = t ; j >= 0 ; j--){ dp[j] = 0; for(int m = 1; m <= k ; m ++ ){ if (j >= m){ dp[j] = (dp[j] + dp[j - m]) % mod; } } } } return dp[t]; } }
总结和习题
通过上面的几个例题，如果大家看了总结的那几个转移方程，则就是会很快秒杀的问题，所以大家写这种基础背包的时候一定要把上面的公式 牢牢掌握 。会对以后的做题绝对有帮助！！！
下面我就直接给大家带来一些练习，加强巩固所学的背包知识问题！！！
习题：
