今日刷题记录
1. 将一个数字表示成幂的和的方案数leetcode.2787
关键词：动态规划
问题分析：
- 要把一个正整数 n 分成不同的数字,这些数的 x 次幂相加为 n,然后对 10e9+7 取余
- 数不同
- 给定幂次
核心思路
- 经典背包问题,选还是不选,选了就把该值加上次幂再减去,我先还是写个记忆化搜索
vector memont(n+1,vector<int>(n+1,-1));
auto dfs = [&](this auto&& dfs,int i,int c)->int{
if(pow(i,x)>n) return c==0;
if(memont[i][c]!=-1) return memont[i][c];
if(c<pow(i,x)) return memont[i][c] = dfs(i+1,c);
return memont[i][c] = (dfs(i+1,c)%mod+dfs(i+1,c-pow(i,x))%mod)%mod;
};
return dfs(1,n)%mod;- 再优化成动态规划,由于不知道遍历次数,只知道遍历结束的条件,pow(i,x)>n 时结束,所以只用一维数组来记录 n 的变化就行
最终代码片段：
vector<int> dp(n+1);
dp[0] = 1;
for(int i = 1,v = 1;v<=n;v = pow(++i,x)){
for(int j = n;j>=v;j--){
dp[j] = (dp[j]%mod+dp[j-v]%mod)%mod;
}
}
return dp[n]%mod;学到的点：
- 老东西
2. 目标和leetcode.494
关键词：动态规划 回溯 背包问题
问题分析：
- 就是给定一个数组,然后选择是加还是减去数组里的元素得到给定值,有多少种选法
- nums{1,2,3} target = 4,则 1-2+3 = 4
核心思路
- 我想到的就是 dfs 中选或者不选,那么就是简单的 dfs
int ans = 0;
int n = nums.size();
auto dfs = [&](this auto&&dfs,int i,int sum)->void{
if(i==n&&sum==0) ans++;
if(i==n) return;
int t =nums[i];
dfs(i+1,sum + t);
dfs(i+1,sum - t);
};
dfs(0,target);
return ans;
//但是就这样也太丑了,试试记忆化吧记忆化之后是什么样呢,我发现我的思路不好记忆化,记忆化的本质是避免重复递归已经解决的子问题,而我上面的代码似乎是遍历了所有的情况,每一个子问题都是不同的,所以不能记忆化 2. 首先我要搞清楚怎么样才能避免全部遍历,只有缩小需求,我们之前是要找到每种正数和负数的情况,两个变量是需求变死了,那么就想数学里的,我们现在是不是要找到某个不变量来替换变量,使题目需求唯一,于是来一个简单的推导
- 把 nums 中的数分为正数 q 和负数 p 部分(为绝对值),那么 q+p = s,target = q - p;
- 上式子中可以化简为,当 target<0 时,q = (s-|target|)/2
- 在这部分中就可以看出我们只需要从 nums 中找出总和为 q 或者 p 的数字就行,那么不是所有的数字要选择,使用递归搜索+保存结果 = 记忆化搜索
- 特判(s+target)/2 这部分,说明 s+target 是 2 的倍数,且 s-|target|>0;
int s = reduce(nums.begin(),nums.end(),0)-abs(target);
if(s<0||s%2) return 0;
int m = s/2;
int n = nums.size();
vector memont(n,vector<int>(m+1,-1));
auto dfs = [&](this auto&&dfs,int i,int c)->int{
if(i<0&&c==0) return 1;
if(i<0) return 0;
if(memont[i][c]!=-1) return memont[i][c];
if(c<nums[i]) return memont[i][c] = dfs(i-1,c);
return memont[i][c] = dfs(i-1,c)+dfs(i-1,c-nums[i]);
};
return dfs(n-1,m);- 还可以简化为动态规划,跟上面的情况一模一样,就是从 0 开始
vector dp(n+1,vector<int>(m+1));
dp[0][0] = 1;
for(int i = 0;i<n;i++){
for(int c = 0;c<=m;c++){
if(c<nums[i]) dp[i+1][c] = dp[i][c];
else dp[i+1][c] = dp[i][c]+dp[i][c-nums[i]];
}
}
return dp[n][m];- 这样的动态规划其实就是一遍遍的遍历树的每一层,当你熟悉了树的层序遍历就会深有感悟,那么层序遍历还有滑动数组的做法,就是两个数组进行轮流交换遍历,这题也是这样,可以继续优化,这样就得到了我们的最终代码,0ms,击败 100%; 代码片段：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int s = reduce(nums.begin(),nums.end(),0)-abs(target);
if(s<0||s%2) return 0;
int m = s/2;
int n = nums.size();
vector dp(2,vector<int>(m+1));
dp[0][0] = 1;
for(int i = 0;i<n;i++){
for(int c = 0;c<=m;c++){
if(c<nums[i]) dp[(i+1)%2][c] = dp[i%2][c];
else dp[(i+1)%2][c] = dp[i%2][c]+dp[i%2][c-nums[i]];
}
}
return dp[n%2][m];
}
};学到的点：
- 0-1 背包模板
- 记忆化搜索
- 动态规划+滑动数组