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

动态规划解题步骤：

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

2.确定状态转移方程：dp[i]等于什么

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

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

5.确定返回值

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

题解：

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]=1size_t n=nums.size();//处理边界条件if(n==1) return 1;//创建dp表vector<int> up(n,1);//最低值为1，所以初始化为1auto 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;}
};