leetcode 376. Wiggle Subsequence | 376. 摆动序列（动态规划）-蒲公英云

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

题目

https://leetcode.com/problems/wiggle-subsequence/
在这里插入图片描述

题解

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

DP 思路

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

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

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

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];
    }
}