建设工程信息网官网新网站,网站制作易捷网络,陕西网站关键词自然排名优化,开网站做备案需要什么资料【LetMeFly】1155.掷骰子等于目标和的方法数#xff1a;动态规划
力扣题目链接#xff1a;https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/
这里有 n 个一样的骰子#xff0c;每个骰子上都有 k 个面#xff0c;分别标号为 1 到 k 。
给定三个整数 …【LetMeFly】1155.掷骰子等于目标和的方法数动态规划
力扣题目链接https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/
这里有 n 个一样的骰子每个骰子上都有 k 个面分别标号为 1 到 k 。
给定三个整数 n , k 和 target 返回可能的方式(从总共 kn 种方式中)滚动骰子的数量使正面朝上的数字之和等于 target 。
答案可能很大你需要对 109 7 取模 。 示例 1
输入n 1, k 6, target 3
输出1
解释你扔一个有 6 个面的骰子。
得到 3 的和只有一种方法。示例 2
输入n 2, k 6, target 7
输出6
解释你扔两个骰子每个骰子有 6 个面。
得到 7 的和有 6 种方法16 25 34 43 52 61。示例 3
输入n 30, k 30, target 500
输出222616187
解释返回的结果必须是对 109 7 取模。 提示
1 n, k 301 target 1000
方法一动态规划(DP)
开辟一个动态规划数组 d p dp dp其中 d p [ i ] [ j ] dp[i][j] dp[i][j]代表 i i i个骰子的和为 j j j的方案数。
初始值 d p [ i ] [ j ] 0 dp[i][j]0 dp[i][j]0而 d p [ 1 ] [ 1 − k ] 1 dp[1][1-k]1 dp[1][1−k]1。
这样我们就可以从第二天开始枚举
for i from 2 to n: # i个骰子for j from 1 to target: # 和为jfor _k from 1 to min(k, target): # i个骰子和为j可以由 i-1个骰子和为j-_k 加上 一个值为_k的骰子 得到dp[i][j] (dp[i][j] dp[i - 1][j - _k]) % MOD优化
不难发现 i i i个骰子的状态只和 i − 1 i-1 i−1个骰子的状态有关因此可以将二维数组压缩为一维。我们初始化了1个骰子从1到k的方案数为1其实我们也可以只领 d p [ 0 ] [ 0 ] 1 dp[0][0]1 dp[0][0]10个骰子和为0的方案数为1
复杂的分析
时间复杂度 O ( n × k × t a r g e t ) O(n\times k\times target) O(n×k×target)空间复杂度 O ( n × t a r g e t ) O(n\times target) O(n×target)或 O ( t a r g e t ) O(target) O(target)
AC代码
C
没有进行空间优化
typedef long long ll;
const ll MOD 1e9 7;
class Solution {
public:int numRollsToTarget(int n, int k, int target) {vectorvectorll dp(n 1, vectorll(target 1, 0));for (int j 1; j min(k, target); j) {dp[1][j] 1;}for (int i 2; i n; i) {for (int j 1; j target; j) {for (int _k 1; _k min(k, j); _k) {dp[i][j] (dp[i][j] dp[i - 1][j - _k]) % MOD;}}}return dp[n][target];}
};Python
进行了空间优化
MOD int(1e9 7)
class Solution:def numRollsToTarget(self, n: int, k: int, target: int) - int:dp [1] [0] * targetfor i in range(1, n 1):for j in range(target, -1, -1):dp[j] 0for _k in range(1, min(k 1, j 1)):dp[j] (dp[j] dp[j - _k]) % MODreturn dp[-1]同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134023955
