学会动态规划按摩师11
目录
动态规划怎么学?
学习一个算法没有捷径,更何况是学习动态规划,
跟我一起刷动态规划算法题,一起学会动态规划!
1. 题目解析
题目链接: 面试题 17.16. 按摩师 - 力扣(Leetcode)
题目不难理解,就是不能选相邻的预约请求,。
最后算出最长的预约时长。
2. 算法原理
1. 状态表示
dp[ i ] 表示的是到这个位置的时候的最长预约时长,
但是实际上这里有两种情况,
1. 到了 i 位置选 i 此时的最长预约时长:我们称之为 f [ i ]
2. 到了 i 位置但是不选 i 此时的最长预约时长:我们称之为 g [ i ]
2. 状态转移方程
那这两种情况的状态转移方程是什么呢?
f [ i ] = g[ i - 1 ] nums[ i ]
g[ i ] = max( f [ i - 1 ],g[ i - 1 ] )
3. 初始化
f [ 0 ] = nums[ 0 ] ,g [ 0 ] = 0
4. 填表顺序
从左往右。
5. 返回值
max( f [ n - 1 ],g[ n - 1 ] ),取最后一个位置的两种情况的最大值
3. 代码编写
-
class Solution {
-
public:
-
int massage(vector<int>& nums) {
-
int size = nums.size();
-
if(size == 0) return 0;
-
vector<int> f(size);
-
auto g = f;
-
f[0] = nums[0];
-
for(int i = 1; i < size; i ) {
-
f[i] = g[i - 1] nums[i];
-
g[i] = max(f[i - 1], g[i - 1]);
-
}
-
return max(f[size - 1], g[size - 1]);
-
}
-
};
写在最后:
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbcha
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13