mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
113 lines
3.5 KiB
Markdown
113 lines
3.5 KiB
Markdown
# [1155. Number of Dice Rolls With Target Sum](https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/)
|
||
|
||
# 思路
|
||
仔细分析一下可知，d个骰子的和为 target 的情况数取决于 d-1 个骰子的和为target-1、target-2...target-f的情况数。所以这题是一个典型的动态规划题。状态定义为
|
||
```
|
||
dp[i][j]: i个骰子的和为j的情况数，dp[0][0]=1
|
||
```
|
||
状态转移方程为：
|
||
```
|
||
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] +...+ dp[i-1][j-f]
|
||
```
|
||
|
||
|
||
## 思路一、自上而下
|
||
|
||
动态规划一般都可以转换成带记忆数组的递归，这题也不例外。
|
||
|
||
时间复杂度O(d * f * target)，空间复杂度O(d * target)
|
||
|
||
## 思路二、自下而上
|
||
更常见的是自下而上，而且我们还可以使用滚动数组对空间进行优化。
|
||
|
||
时间复杂度O(d * f * target)，空间复杂度O(target)
|
||
|
||
## 思路三
|
||
思路二一共有三层循环，可以进一步优化时间。
|
||
|
||
回顾一下状态转移方程，
|
||
```
|
||
dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] +...+ dp[i-1][j-f]
|
||
|
||
j++后:
|
||
dp[i][j+1] = dp[i-1][j] + dp[i-1][j-1] +...+ dp[i-1][j-f+1]
|
||
```
|
||
所以说连续两次运行第三次循环是有大量重复的，所以第三层循环不是必须的。
|
||
|
||
可以这样考虑，`dp[i][j]` 的计算就是求一个大小为 f 的在数组`dp[i-1]`上的滑动窗口的元素和，思路二的第三层循环每次都从头到尾累加窗口内的元素，但事实上我们可以维护一个变量s代表窗口内元素的和，当窗口向右滑动一步时我们只需要将s加上窗口右端元素然后减去刚刚离开窗口左端的元素即可。
|
||
|
||
时间复杂度O(d * target)，空间复杂度O(target)
|
||
|
||
# C++
|
||
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
vector<vector<int>>dp = vector<vector<int>>(31, vector<int>(1001, -1));
|
||
public:
|
||
int numRollsToTarget(int d, int f, int target) {
|
||
if(target < 0 || target > d * f) return 0;
|
||
if(d == 0) return target == 0 ? 1 : 0;
|
||
|
||
if(dp[d][target] >= 0) return dp[d][target];
|
||
int res = 0;
|
||
for(int i = 1; i <=f; i++){
|
||
res += numRollsToTarget(d - 1, f, target - i);
|
||
res %= 1000000007;
|
||
}
|
||
|
||
dp[d][target] = res;
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int numRollsToTarget(int d, int f, int target) {
|
||
if(target > d * f) return 0; // 会大大减少测试时间
|
||
|
||
vector<int>dp(target+1, 0);
|
||
dp[0] = 1;
|
||
for(int i = 1; i <= d; i++)
|
||
for(int j = target; j >= 0; j--){ // 注意这里要反向遍历!
|
||
int max_k = min(j, f); dp[j] = 0;
|
||
for(int k = 1; k <= max_k; k++){
|
||
dp[j] += dp[j-k];
|
||
dp[j] %= 1000000007;
|
||
}
|
||
}
|
||
return dp[target];
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路三
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int numRollsToTarget(int d, int f, int target) {
|
||
const int M = 1000000007;
|
||
|
||
// dp表示dp[i][...], pre代表dp[i-1][...]
|
||
vector<int> dp(target + 1, 0), pre(target + 1, 0);
|
||
dp[0] = 1;
|
||
long long s = 0;
|
||
for(int i = 1; i <= d; i++){
|
||
for(int t = 0; t <= target; t++) pre[t] = dp[t];
|
||
|
||
s = 0;
|
||
for(int j = 0; j <= target; j++){
|
||
dp[j] = s;
|
||
s += pre[j]; // 累加上窗口右端元素
|
||
if(j >= f) s += M - pre[j - f]; // 减去刚刚离开窗口左端的元素
|
||
s %= M;
|
||
}
|
||
}
|
||
return dp[target];
|
||
}
|
||
};
|
||
``` |