中文网站模板下载,西宁百姓网免费发布信息,网站意见反馈源码,中国互联网协会秘书长本篇文章我们继续学习动态规划 第一题
题目链接
978. 最长湍流子数组 - 力扣#xff08;LeetCode#xff09;
题目解析 从上图可见其实有三个状态
代码原理 注意#xff1a;我们在分析题目的时候分析出来的是三个状态#xff0c;分别是上升、下降、平坦#xff0c;但是…本篇文章我们继续学习动态规划 第一题
题目链接
978. 最长湍流子数组 - 力扣LeetCode
题目解析 从上图可见其实有三个状态
代码原理 注意我们在分析题目的时候分析出来的是三个状态分别是上升、下降、平坦但是不一定要定义三个状态表示一个不够加一个直到可以解决这道题为止
代码编写
class Solution {
public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); vectorint f(n, 1); auto g f; int ret 1; for(int i 1; i n; i) { if(arr[i] arr[i - 1])f[i] g[i - 1] 1; else if(arr[i] arr[i - 1])g[i] f[i - 1] 1; ret max(ret, max(f[i], g[i])); } return ret; }
};
第二题
题目链接
413. 等差数列划分 - 力扣LeetCode
题目解析 代码原理 代码编写
class Solution {
public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); vectorint dp(n); int count 0; for(int i 2; i n; i) { dp[i] nums[i] - nums[i - 1] nums[i - 1] - nums[i - 2]? dp[i - 1] 1:0; count dp[i]; } return count; }
};
第三题
题目链接
139. 单词拆分 - 力扣LeetCode
题目解析 代码原理 代码编写
class Solution {
public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring hash; for(auto cur: wordDict) hash.insert(cur); int n s.size(); vectorbooldp(n 1); dp[0] true; s s;//保证字符串的长度与dp表的长度一致 for(int i 1; i n; i) { for(int j i; j 1; j--) { if(dp[j - 1] hash.count(s.substr(j, i - j 1))) { dp[i] true; break; } } } return dp[n]; }
};
本篇文章的内容就先到这里我们下期文章再见 记得一键三联哦
