leet code每日一题,leet code
终极管理员 知识笔记 68阅读
力扣题目链接
这里有 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: # 和为j for _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) { vector<vector<ll>> dp(n 1, vector<ll>(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]; }};进行了空间优化
MOD int(1e9 7)class Solution: def numRollsToTarget(self, n: int, k: int, target: int) -> int: dp [1] [0] * target for i in range(1, n 1): for j in range(target, -1, -1): dp[j] 0 for _k in range(1, min(k 1, j 1)): dp[j] (dp[j] dp[j - _k]) % MOD return dp[-1]同步发文于原创不易转载经作者同意后请附上原文链接哦~
Tisfy