leetcode1155.掷骰子等于目标和的方法数

题目如下

数据范围

显然本题可以使用动态规划 令f(i,j)为投掷i次骰子走到j处的方法数 则f(i,j) = f(i - 1,j - 1) + f(i,j - 2) + ..... + f(i,j - k) 所以可以利用一个二维数组计算来转移。 但是由于每次计算都只会用到上一行的数据， 所以可以利用滚动数组的思想从后往前更新减少空间复杂度。

通过代码

class Solution { public: int numRollsToTarget(int n, int k, int target) { if (n * k < target) return 0; if (n * k == target) return 1; if(n == 1)return 1; vector<int> dp(target + 1,0); for(int i = 1;i <= min(k,target);i++)dp[i] = 1; int mod = 1e9 + 7; for (int i = 1; i < n; i++) { for (int j = target; j >= 1; j--) { dp[j] = 0; for (int l = 1; l <= k; l++) { if (j > l) { dp[j] = (dp[j] + dp[j - l]) % mod; } } } } return dp[target]; } };