leetcode 376. Wiggle Subsequence | 376. 摆动序列（动态规划）

旧城等待， 2022-08-31 02:19 136阅读 0赞

## 题目 ##

[https://leetcode.com/problems/wiggle-subsequence/][https_leetcode.com_problems_wiggle-subsequence]  
![在这里插入图片描述][59bb70141c029d179e7d0b7eea27c21e.png]

## 题解 ##

刷题大概确实是有效果的吧…  
印象中，这算是今日第二道，全局第三道没看答案写出来的 dp …  
找到 dp 的套路，总会有让 dp 不再成为玄学的那一天，指日可待…

##### DP 思路 #####

也不全是自己想的思路。这道题与 [leetcode 300. Longest Increasing Subsequence | 300. 最长递增子序列（动态规划）][leetcode 300. Longest Increasing Subsequence _ 300.]非常类似，思路很大程度上受到了这道题的启发，也就是在计算连续子序列的问题时，dp 用来记录强制包含当前元素时的最长子序列长度。

与 **第 300 题 “最长递增子序列”** 不同的是，本题要求子序列 **增减性不断交替**，所以还需要考虑 **前一个序列的末尾元素的增减性**。为此，我们创建一个 incr\[\] 数组，incr\[j\] 用来记录当前 j 位置最长子序列的末尾元素的增减性，以便和后面 j 位置上的元素相呼应。

顺便贴上几乎看不懂的草稿，记录一下“尝试”的过程（对于 dp 问题，可以先用前几个数尝试一下，找感觉）  
![在这里插入图片描述][37ab383a121388044cab860d851e1d89.png]

class Solution { 
        public int wiggleMaxLength(int[] nums) { 
            if (nums.length == 1) return 1;
            if (nums.length == 2) return nums[0] == nums[1] ? 1 : 2;
    
            boolean[] incr = new boolean[nums.length];
            int[] dp = new int[nums.length];
    
            dp[0] = 1;
            for (int i = 1; i < dp.length; i++) { 
                dp[i] = 1;
                for (int j = 0; j < i; j++) { 
                    if (nums[j] == nums[i]) continue;
                    if (j == 0 || incr[j] == nums[j] > nums[i]) { 
                        if (dp[i] < dp[j] + 1) { 
                            dp[i] = dp[j] + 1;
                            incr[i] = nums[j] < nums[i];
                        }
                    }
                }
            }
            return dp[dp.length - 1];
        }
    }

![在这里插入图片描述][290f0d071a0b0aa68664434efb67dda8.png]

[https_leetcode.com_problems_wiggle-subsequence]: https://leetcode.com/problems/wiggle-subsequence/
[59bb70141c029d179e7d0b7eea27c21e.png]: /images/20220829/2010fbcd7a094f5b9c0bc2489b3e41ae.png
[leetcode 300. Longest Increasing Subsequence _ 300.]: https://blog.csdn.net/sinat_42483341/article/details/118487526
[37ab383a121388044cab860d851e1d89.png]: /images/20220829/5f98508f95c04e8eaa19ca7efc106d19.png
[290f0d071a0b0aa68664434efb67dda8.png]: /images/20220829/cf4c4c86d5524d0db8843742f8b0c969.png