【学会动态规划】摆动序列（27）-Toy模板网

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

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：376. 摆动序列 - 力扣（LeetCode）

【学会动态规划】摆动序列（27）,学会动态规划,动态规划,算法

这道题很好理解，他需要找数字之间的差是一个正数一个负数的交替，

其实我们不用想的这么麻烦，可以把它看成是一个递增递减递增递减交替的一个序列。

然后不要忘记这要找的是子序列，是可以跳着找的。

2. 算法原理

1. 状态表示

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

但是他实际上分为两种情况：

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

g [ i ] 表示以 i 位置为结尾，最后一个位置呈现 “下降” 趋势的最长摆动序列的长度。

2. 状态转移方程

状态转移方程还是分成两大类：

先从 f [ i ] 开始说起：

f [ i ] 可以自己本身作为一个子序列，长度就是 1

f [ i ] 可以和自己前面的任意一个数一起成为子序列，长度就是 g [ i - 1 ] + 1

这里要注意的是，需要 f [ i - 1 ] < f [ i ]

然后是 g [ i ] :

g [ i ] 可以自己本身作为一个子序列，长度就是 1

g [ i ] 可以和自己前面的任意一个数一起成为子序列，长度就是 f [ i - 1 ] + 1

这里要注意的是，需要 g [ i - 1 ] > g [ i ]

3. 初始化

我们只要都设成 1，就能不用考虑第一种情况。

4. 填表顺序

从左往右。

5. 返回值

返回 f 表和 g 表中的最大值。

3. 代码编写

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size(), fmax = 1, gmax = 1;
        vector<int> f(n, 1), g(n, 1);
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) f[i] = max(f[i], g[j] + 1);
                if(nums[i] < nums[j]) g[i] = max(g[i], f[j] + 1);
            }
            fmax = max(fmax, f[i]);
            gmax = max(gmax, g[i]);
        }
        return max(fmax, gmax);
    }
};