今日学习记录
1. 掷骰子等于目标和的方法数leetcode.1155
关键词：背包
问题分析：
- 有 n 个相同的数组,每个数组由 1~k 的数组成,要从 n 个数组中选出一个数相加为 target
核心思路
- 一看就是搜索,但是我要搜索所有选了 n 个数组之后的不同值,看其是否等于 target,所以是一个分组背包的问题,还是选或不选,可以直接分组选,定义 dfs(i,s),i 为次数,s 为剩下的和
const int MOD = 1000000007;
int numRollsToTarget(int n, int k, int target) {
if(target<n||target>n*k) return 0;
auto dfs = [&](this auto&&dfs,int i,int s)->int{
if(i==0) return s==0;
int res = 0;
for(int x = 0;x<k&&x<=s;x++){
res = (res+dfs(i-1,s-x))%MOD;
}
return res%MOD;
};
return dfs(n,target-n);
}- 试试记忆化,记忆化的话就是记录 dfs 的状态,只要 dfs 的状态定义对了,记忆化就不会出问题,对于一般的题目,记忆化效率还是挺高的
const int MOD = 1000000007;
int numRollsToTarget(int n, int k, int target) {
if(target<n||target>n*k) return 0;
vector arr(n+1,vector<int>(target+1,-1));
auto dfs = [&](this auto&&dfs,int i,int s)->int{
if(i==0) return s==0;
int &res = arr[i][s];
if(res!=-1) return res;
res = 0;
for(int x = 0;x<k&&x<=s;x++){
res = (res+dfs(i-1,s-x))%MOD;
}
return res%MOD;
};
return dfs(n,target-n);
}- 翻译成递推,动态规划,定义的状态与 dfs 的记忆化是一样的,其实 dfs 的记忆化就是动态规划的一种形式,但是一般的 dfs 思考是从主问题向子问题发散搜索(递),到最后搜索到头了才返回答案(归),但是动态规划是直接从子问题出发往主问题上收集答案,去掉了递只留下了归 对 dfs 的定义同样能用于 dp 的状态定义,本质上思想是一样的,把搜索的过程量变为循环,把 dfs 的边界问题变为 dp 中的初始化值,说的倒容易,但是其实要大量练习训练体会才能懂
const int MOD = 1000000007;
int numRollsToTarget(int n, int k, int target) {
if(target<n||target>n*k) return 0;
vector dp(n+1,vector<int>(target-n+1));
dp[0][0] = 1;
for(int i = 1;i<=n;i++){
for(int s = 0;s<=target-n;s++){
for(int x = 0;x<k&&x<=s;x++){
dp[i][s] = (dp[i][s]+dp[i-1][s-x])%MOD;
}
}
}
return dp[n][target-n];
}- 肯定不会止步于此,还能进一步优化,别忘了动态规划的最抽象操作,二维 dp 压缩成一维 dp,此操作需要深入完全理解 dp 的状态方程,发现规律和优化空间才行
我们来回顾一下,状态方程的原式
- 可以发现 i-1 不变,而 j 在递减,把不变量去掉,组成前缀和,边界最小为 0 嘛
- 继续化:,那么这个新的状态方程就找到了
- 当 j>=k: ,上限为 j-k+1;
- 当 j<k: ,上限为 0,所以恒为;
const int MOD = 1000000007;
int numRollsToTarget(int n, int k, int target) {
if(target<n||target>n*k) return 0;
vector<long long> dp(target-n+1);
dp[0] = 1;
for(int i = 1;i<=n;i++){
int mn = min(target-n,i*(k-1));
//处理前缀和
for(int j = 1;j<=mn;j++) dp[j] = dp[j-1]+dp[j];
//开始处理f[i][j],减去k取0到k范围内的值,取完后,前面的值就没用了,这也是一维dp的优势
for(int x = mn;x>=k;x--) dp[x] =(dp[x]-dp[x-k])%MOD;
}
return dp[target-n];
}学到的点：
- dfs 转动态规划