C++算法第十六天
本篇文章我们继续学习动态规划
第一题
题目链接
978. 最长湍流子数组 - 力扣（LeetCode）
题目解析
从上图可见其实有三个状态
代码原理
注意：我们在分析题目的时候分析出来的是三个状态，分别是上升、下降、平坦，但是不一定要定义三个状态表示，一个不够加一个，直到可以解决这道题为止
代码编写
class Solution {
public:
int maxTurbulenceSize(vector<int>& arr) {
int n = arr.size();
vector<int> 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(vector<int>& nums) {
int n = nums.size();
vector<int> 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, vector<string>& wordDict) {
unordered_set<string> hash;
for(auto cur: wordDict) hash.insert(cur);
int n = s.size();
vector<bool>dp(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];
}
};
本篇文章的内容就先到这里，我们下期文章再见！！！
记得一键三联哦！！！
