海关企业信息查询网站,郑州网站商城建设,鞍山玉佛苑玉佛图片,四川省城乡建设网网站[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍 文章目录 [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍题目分析题目解析状态表示状态转移方程初始化和填表顺序 代码实现按摩师打家劫舍 总结 注#xff1a;本题与…[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍 文章目录 [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍题目分析题目解析状态表示状态转移方程初始化和填表顺序 代码实现按摩师打家劫舍 总结 注本题与打家劫舍基本一样所以只写一道按摩师末尾只会加上打家劫舍1的代码。
面试题 17.16. 按摩师 198. 打家劫舍
题目分析
(1) 按摩师不能连续接预约
(2) 按摩师可以选择接或者不接预约
(3) 返回预约时间最长的分钟数
题目解析
状态表示
dp[i]按往常的经验以i为结尾的最大的服务的分钟数
dp[i]又可以分为
f[i]到i位置接第i次预约的服务的最大分钟数g[i]到i位置不接第i次预约的服务的最大分钟数
状态转移方程
f[i]:
f[i]是到i位置必须接i位置的服务的最大分钟数。
由于不能连续接受服务所以接了i位置i-1位置就不能接受预约了。
g[i-1]正好是到i-1位置且不接受i-1预约的最大分钟数再加上对应的i位置的分钟数就是f[i]。(可以参考后面的图)
f[i] g[i-1] nums[i]g[i]:
g[i]是到i位置不接i位置的服务的最大分钟数。
由于不接i位置所以只能看i-1位置。而i-1位置也分为接或者不接。
接i-1位置为f[i-1] (参考状态表示)不接i-1为g[i-1] (参考状态表示)。
由于求最大值取它们两个较大的值即可。(可以参考后面的图)
g[i] max(f[i-1], g[i-1])初始化和填表顺序
初始化访问i-1所以一般初始化前面的位置。
i 0时参考状态表示
f[0] nums[0], g[0] 0填表顺序
从左向右填表。
看到这里大家可以尝试实现代码再来看接下来的内容。 代码实现
按摩师
class Solution {
public:int massage(vectorint nums) {//创建dp数组int n nums.size();if(n 0) return 0;vectorint f(n);//选到i位置必选ivectorint g(n);//选到i位置不选i//初始化f[0] nums[0], g[0] 0;//填表for(int i 1; i n; i){g[i] max(f[i-1], g[i-1]);f[i] g[i-1] nums[i];}//返回值return max(g[n-1], f[n-1]);}
};打家劫舍
class Solution {
public:int rob(vectorint nums) {//创建dp数组int n nums.size();vectorint f(n);vectorint g(n);//初始化f[0] nums[0], g[0] 0;//填表for(int i 1; i n; i){f[i] g[i-1] nums[i];g[i] max(g[i-1], f[i-1]);}//返回值return max(f[n-1], g[n-1]);}
};总结
细节注重将问题细分加上画图理解即可。
