网站制作关键词,常州微网站开发,大庆做流产油城女子网站,湖州做网站建设的公司哪家好文章目录 Tag题目来源题目解读解题思路方法一#xff1a;动态规划 写在最后 Tag
【动态规划】【数组】 题目来源
1155. 掷骰子等于目标和的方法数 题目解读
你手里有 n 个一样的骰子#xff0c;每个骰子都有 k 个面#xff0c;分别标号 1 到 n。给定三个整数 n#xff0… 文章目录 Tag题目来源题目解读解题思路方法一动态规划 写在最后 Tag
【动态规划】【数组】 题目来源
1155. 掷骰子等于目标和的方法数 题目解读
你手里有 n 个一样的骰子每个骰子都有 k 个面分别标号 1 到 n。给定三个整数 nk 和 target返回这个 n 个骰子正面朝上的数字组成 target 的所有方案数。答案可能很大返回对 1 e 9 7 1e97 1e97 取模后的值。 解题思路
方法一动态规划
我们可以使用动态来解决本题。
状态
记 f[i][j] 表示使用 i 个骰子且数字和为 j 的方案数。
转移关系
我们可以枚举最后一个骰子的数字数字的范围在 [1, k]使用 i 个骰子组成的数字和为 j 的方案数为: f [ i , j ] ∑ x 1 k f [ i − 1 ] [ j − k ] f\left[ i,j \right] \sum_{x1}^k{f\left[ i-1 \right] \left[ j-k \right]} f[i,j]x1∑kf[i−1][j−k]
base case
f[0][0] 1计即我们还没有掷骰子数字之和为 0 时的方案数。
最终返回
最终返回 f[n][target]表示使用 n 个骰子正面朝上的数字组成 target 的所有方案数
实现代码
class Solution {
public:int numRollsToTarget(int n, int k, int target) {if (target n || target n * k) {return 0;}const int MOD 1e9 7;vectorvectorint f(n1, vectorint(target1));f[0][0] 1;for (int i 1; i n; i) {for (int j 0; j target; j) {for (int x 1; x k; x) {if (j - x 0) {f[i][j] (f[i][j] f[i-1][j-x]) % MOD;}}}}return f[n][target];}
};优化
注意观察状态转移方程f[i][j] 只会从 f[i-1, ...] 转移过来因此只需要存储第 i 行和第 i-1 行的值使用两个一维数组代替二维数组进行转态转移。
class Solution {
public:int numRollsToTarget(int n, int k, int target) {if (target n || target n * k) {return 0;}const int MOD 1e9 7;vectorint f(target 1);f[0] 1;for (int i 1; i n; i) {vectorint g(target 1);for (int j 0; j target; j) {for (int x 1; x k; x) {if (j - x 0) {g[j] (g[j] f[j-x]) % MOD;}}}f g;}return f[target];}
};复杂度分析
时间复杂度 O ( n ⋅ k ⋅ t a r g e t ) O(n \cdot k \cdot target) O(n⋅k⋅target)。
空间复杂度 O ( n ⋅ t r a g e t ) O(n \cdot traget) O(n⋅traget)优化后的空间复杂度为 O ( t a r g e t ) O(target) O(target)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
