今日学习记录
1. 执行操作可获得的最大总奖励 Ileetcode.3180
关键词：背包
问题分析：
- 从数组中选一些数,要求只能加上比原来累加值更大的值,求最大累加值
核心思路
- 还是背包问题,选还是不选,直接写很简单的 dfs,一般会超时
int maxTotalReward(vector<int>& rewardValues) {
//老规矩,先排序
//要大,肯定要先选小的再选大的
ranges::sort(rewardValues);
int n = rewardValues.size();
auto dfs = [&](this auto&&dfs,int i,int sum)->int{
if(i<0||i>=n) return sum;
//可选也可以不选
if(rewardValues[i]>sum){
return max(dfs(i+1,sum),dfs(i+1,sum+rewardValues[i]));
}else return dfs(i+1,sum);
};
return dfs(0,0);
}- 可以使用记忆化,记录哪些选项选择过
int maxTotalReward(vector<int>& rewardValues) {
//老规矩,先排序
//要大,肯定要先选小的再选大的
ranges::sort(rewardValues);
int n = rewardValues.size();
int mx = rewardValues[n-1];
vector arr(n+1,vector<int>(mx+1,-1));
auto dfs = [&](this auto&&dfs,int i,int sum)->int{
if(sum>=mx||i>=n) return sum;
int& mt = arr[i][sum];
if(mt!=-1) return mt;
//可选也可以不选
if(rewardValues[i]>sum){
mt = dfs(i+1,sum+rewardValues[i]);
}
return mt = max(mt,dfs(i+1,sum));
};
return dfs(0,0);
}学到的点：
- 背包