动态规划28：376. 摆动序列

解题步骤：

1.确定状态表示：dp[i]是什么

2.确定：dp[i]等于什么

3.：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：

题解：

1.状态表示： up[i]表示以nums[i]结尾的子序列中上升摆动序列的最长子序列长度
                      down[i]表示以nums[i]结尾的子序列中下降摆动序列的最长子序列长度

2.状态转移方程：见代码分析

3.初始化：由于up表和down表的最低值为1，所以创建表时就将两个表初始化为1

4.填表顺序：从左向右，两个表依次填写

5.返回值：返回up表和down表中的最大值

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        //上升摆动子序列：最后两个元素之间是a<b
        //下降摆动子序列：最后两个元素之间是a>b
        //up[i]表示以nums[i]结尾的子序列中上升摆动序列的最长子序列长度
        //down[i]表示以nums[i]结尾的子序列中下降摆动序列的最长子序列长度
        //如果以nums[i]结尾的子序列要成为上升摆动子序列
        //则必须存在nums[j]<nums[i] 0=<j<i
        //即以nums[j]为结尾的下降摆动子序列
        //up[i]=down[j]+1
        //由于以nums[j]为结尾的下降摆动子序列可能有多个
        //所以up[i]=max(up[i],down[j]+1)
        //如果不存在nums[j]<nums[i] up[i]=1

        //如果以nums[i]结尾的子序列要成为下降摆动子序列
        //则必须存在nums[j]>nums[i] 0=<j<i
        //即以nums[j]结尾的上升摆动子序列
        //down[i]=up[j]+1
        //由于nums[i]结尾的子序列要成为上升摆动子序列
        //down[i]=max(down[i],up[j]+1)
        //如果不存在nums[j]>nums[i] down[i]=1
        
        size_t n=nums.size();
        //处理边界条件
        if(n==1) return 1;
        //创建dp表
        vector<int> up(n,1);//最低值为1，所以初始化为1
        auto down=up;
        //初始化
        up[0]=down[0]=1;
        //填表
        for(int i=1;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(nums[j]<nums[i]) 
                {
                    up[i]=max(up[i],down[j]+1);
                }
                else if(nums[j]>nums[i])
                {
                    down[i]=max(down[i],up[j]+1);
                }
            }
        }
        //返回值
        int ans=0;
        for(auto e:up) if(e>ans) ans=e;
        for(auto e:down) if(e>ans) ans=e;
        return ans;
    }
};