dfv印花图案设计网站,网站建设应该应聘什么岗位,vps上安装wordpress,政务公开 加强门户网站建设目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接978. 最长湍流子数组 - 力扣LeetCode 题目说要找出最长的湍流子数组但是他的题干太长了而且不止所云
所以我们直接通过用例来分析什么是湍流子数组
通过示例一我们知道了湍流子数组就是一个大一小一个大一个小的子数组
通过示例二我们知道了如果数组一直是递增/递减最长就是 2
通过示例三我们知道了如果数组只有一个元素那么长度就是 1。
2. 算法原理
1. 状态表示
我们还是从 dp [ i ] 来分析
dp [ i ] 表示以 i 位置为结尾的所有子数组中最长的湍流子数组的长度。
实际上他一共存在两种情况
f [ i ] 表示 i 位置为结尾的所有子数组中上升状态时最长的湍流子数组的长度
g [ i ] 表示 i 位置为结尾的所有子数组中下降状态时最长的湍流子数组的长度
2. 状态转移方程
f [ i ] 分为三种情况
当 f [ i - 1 ] f [ i ] 要想进入上升状态就得重新计算所以变成 1
当 f [ i - 1 ] f [ i ] 下降状态的最长长度就是 g [ i - 1 ] 1
当 f [ i - 1 ] f [ i ] 要想进入平缓状态就得重新计算所以变成 1
g [ i ] 也同样是这三种情况
当 g [ i - 1 ] g [ i ] 上升状态的最长长度就是 f [ i - 1 ] 1
当 g [ i - 1 ] g [ i ] 要想进入下降状态就得重新计算所以变成 1
当 g [ i - 1 ] g [ i ] 要想进入平缓状态就得重新计算所以变成 1
3. 初始化
我们可以把所有位置先初始化成 1 作为初始值
4. 填表顺序
从左往右两个表一起填。
5. 返回值
返回两个表里面的最大值。
3. 代码编写
class Solution {
public:int maxTurbulenceSize(vectorint arr) {int n arr.size();vectorint f(n, 1), g(n, 1);int ans 1;for(int i 1; i n; i) {if(arr[i - 1] arr[i]) f[i] g[i - 1] 1;else if(arr[i - 1] arr[i]) g[i] f[i - 1] 1;ans max(ans, max(f[i], g[i]));}return ans;}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
