动态规划dp —— 28.摆动序列-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划dp —— 28.摆动序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划dp —— 28.摆动序列,动态规划,动态规划,算法

连续相同的数不算是摆动序列

单独一个或不相等的两个数算是摆动序列

1.状态表示

是什么？dp表中里的值所表示的含义就是状态表示

dp[i]表示：以i位置为结尾的所有子序列中，最长的摆动序列的长度

但是i位置的值可能是下降后的，也可能是上升后的，所以细分为两种状态表示

f[i]表示:以i位置为结尾的所有子序列中，最后一个位置呈现“上升”趋势最长的摆动序列的长度

f[i]表示:以i位置为结尾的所有子序列中，最后一个位置呈现“下降”趋势最长的摆动序列的长度

动态规划dp —— 28.摆动序列,动态规划,动态规划,算法

2.状态转移方程

dp[i] 等于什么

根据子序列长度不同，可分为两种情况：1.长度为1 2.长度大于1

动态规划dp —— 28.摆动序列,动态规划,动态规划,算法

因为一个位置到i位置是上升趋势的，所以到i位置的前一个位置一定是下降的，所以刚好就是状态表示的g表，j表示子序列i位置的前一个位置（可能有很多），要找到最大的然后+1

g表同理：

动态规划dp —— 28.摆动序列,动态规划,动态规划,算法

3.初始化

保证填表的时候不越界

f表和g表全部初始化为1，这样就不用考虑长度为1的情况了

4.填表顺序

为了填写当前状态的时候，所需要的状态已经计算过了

从左往右，两个表一起填

5.返回值

题目要求+状态表

两个表里的最大值文章来源地址https://www.toymoban.com/news/detail-653832.html

6.代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        //1.创建dp表
        //2.初始化
        vector<int> f(n,1);
        vector<int> g(n,1);
        //3.填表
        int ret = 1;
        for(int i = 1; i < n;i++)
        {
            for(int j = 0; j < i;j++)
            {
                if(nums[i]> nums[j])
                {
                    f[i] = max(g[j]+1,f[i]);
                }
                else if(nums[i] < nums[j])
                {
                    g[i] = max(f[j] + 1,g[i]);
                }
            }
            ret = max(ret, max(f[i],g[i]));
        }
        //4.返回值
        return ret;
    }
};

到了这里，关于动态规划dp —— 28.摆动序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！