舟山网站建设,规模以上工业企业个数,网站建设 网站推广,电脑科技网站模板[动态规划] (十三) 简单多状态: LeetCode 740.删除并获得点数 文章目录 [动态规划] (十三) 简单多状态: LeetCode 740.删除并获得点数题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结 740. 删除并获得点数 题目解析
(1) 给定一个整数数组。
(2) 选…[动态规划] (十三) 简单多状态: LeetCode 740.删除并获得点数 文章目录 [动态规划] (十三) 简单多状态: LeetCode 740.删除并获得点数题目解析解题思路状态表示状态转移方程初始化和填表顺序返回值 代码实现总结 740. 删除并获得点数 题目解析
(1) 给定一个整数数组。
(2) 选择一个nums[i]获得所有nums[i]的和删除nums[i] - 1和nums[i] 1。
(3) 一开始你有0个点数返回你能获得的最大点数
解题思路
通过题目解析我们发现这和我们之前做的打家劫舍和按摩师有一些共同之处。
假设一个数组是[1234]如果我们选择了3那就不能选择2和4。
那么我们把这个重复出现的数字归到同一下标位置是不是就可以将它转换为打家劫舍问题呢(预处理)我们来试试 我们可以取2-0-5-7或者2-8-12-24等等情况这就和我们之前做的打家劫舍几乎一模一样了。
状态表示
dp[i]按照往常的经验以i为终点可以获得的最大点数。
i位置我们有可以选择获取或者不获取
f[i]:表示获取i位置的点数
g[i]:表示不获取i位置的点数
状态转移方程
f[i]当我们需要获取i位置的点数时那么i-1位置必然不获取。
所以我们只用i-1之前的点数加上对应当前位置的点数即可。
f[i] g[i-1] nums[i]g[i]当我们不获取i位置时那么i-1位置又可以获取也可以不获取我们只需要取最大值即可。对应状态表示获取i-1位置就是f[i-1]不获取i-1就是g[i-1]
g[i] max(f[i-1] g[i-1])初始化和填表顺序
初始化
因为我们在刚刚举例子时发现新的数组会多出一个0位置的元素所以我们可以多初始化一个虚拟节点这可以让我们下标对应更加简单。
我们把虚拟出的节点初始化为0即可容器在扩容时又会自动帮我们初始化为0所以我们不需要手动初始化。
填表顺序
从左到右。
返回值
多了一个虚拟节点返回n位置的较大值即可。
看到这里可以尝试手动实现代码再来看下面的内容。 代码实现
class Solution {
public:int deleteAndEarn(vectorint nums) {//预处理const int cnt 10001;int arr[cnt] {0};for(auto e : nums) arr[e] e;//创建dp表vectorint f(cnt);vectorint g(cnt);//初始化// f[0] arr[0], g[0] 0;//填表for(int i 1; i cnt; i){f[i] g[i-1] arr[i];g[i] max(f[i-1], g[i-1]);}//返回值return max(f[cnt-1], g[cnt-1]);}
};总结
细节1多多联系我们之前做过的题看看新的题与我们之前做过的题有没有什么通性。
细节2预处理数组的空间我们比题目给的多扩了1个所以返回值n位置即为我们扩的容量-1。
