黔西县住房和城乡建设局网站,qq推广中心,深圳宝安区做网站,wordpress后端页面开发1. 按摩师 题目链接#xff1a; 面试题 17.16. 按摩师 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/the-masseuse-lcci/description/ 2. 算法原理 状态表示#xff1a;以某一个位置为结尾或者以某一个位置为起点 dp[i]表示#xff1a;选择到i位置…1. 按摩师 题目链接 面试题 17.16. 按摩师 - 力扣LeetCodehttps://leetcode.cn/problems/the-masseuse-lcci/description/ 2. 算法原理 状态表示以某一个位置为结尾或者以某一个位置为起点 dp[i]表示选择到i位置的时候此时的最长预约时长分两种情况 1.f[i]表示选择到i位置的时候当前位置nums[i]必选此时的最长预约时长 2.g[i]表示选择到i位置的时候当前位置nums[i]不选此时的最长预约时长 2. 状态转移方程 根据最近的一步来划分问题 到达dp[i][j]有两种情况 1. f[i]g[i-1] nums[i] 2. g[i]a. 当选择i-1的位置时f[i-1] b.当不选择i-1的位置时g[i-1] g[i]max(f[i-1],g[i-1]) 3. 初始化 把dp表填满不越界让后面的填表可以顺利进行 本题初始化为f[0]nums[0] g[0]在vector填表的时候默认为0 4. 填表顺序 本题的填表顺序是从左往右两个表一起填 5. 返回值 题目要求 状态表示 本题的返回值是max(f[n-1],g[n-1]) 3.代码 动态规划的固定四步骤1. 创建一个dp表 2. 在填表之前初始化 3. 填表填表方法状态转移方程 4. 确定返回值 class Solution {
public:int massage(vectorint nums) {int nnums.size();//处理一下边界情况if(n0) return 0;vectorintf(n);auto gf;f[0]nums[0];for(int i1;in;i){f[i]g[i-1]nums[i];g[i]max(f[i-1],g[i-1]);}return max(f[n-1],g[n-1]);}
}; 完结撒花~
