# 2369. Check if There is a Valid Partition For The Array
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array/description/
## 思路
### 没有空间优化 $O(N)$ $O(N)$
典型dp问题
对于当前数字```nums[i]``` 我们要查看```nums[i-1]```和它是否相等 如果相等并且```nums[0:i-2]```有valid partition ```nums[0:i]```也有valid partition
对于当前数字```nums[i]``` 我们要查看```nums[i-1]```和```nums[i-2]```和它是否相等 如果相等并且```nums[0:i-3]```有valid partition ```nums[0:i]```也有valid partition
对于当前数字```nums[i]``` 我们要查看```nums[i-2]```, n```ums[i-1]```和```nums[i]```能否构成increasing consecutive sequence, 如果可以并且```nums[0:i-3]```有valid partition ```nums[0:i]```也有valid partition
### 空间优化 $O(N)$ $O(1)$
rolling dp
参考[这里](https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array/solutions/2390497/dp/
)
因为我们只需要dp[i-1], dp[i-2]就可以得到dp[i+1]
因此我们只要维护一个size为4的dp array即可
## Code
### 没有空间优化

class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i=0; i<n; i++){
            if(i>0 && nums[i]==nums[i-1] && dp[i-1]) dp[i+1]=true;
            else if(i>1 && nums[i]==nums[i-1] && nums[i-1]==nums[i-2] && dp[i-2]) dp[i+1] = true;
            else if(i>1 && nums[i]==nums[i-1]+1 && nums[i-1]==nums[i-2]+1 && dp[i-2]) dp[i+1] = true;
        }
        return dp[n];
    }
}

### 空间优化

class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        if(n==1) return false;
        boolean[] dp = new boolean[]{true, false, nums[0]==nums[1], false};
        for(int i=2; i<n; i++){
            boolean two = nums[i]==nums[i-1];
            boolean three = (two && nums[i]==nums[i-2]) || (nums[i-1]+1==nums[i] && nums[i-2]+1==nums[i-1]);
            dp[(i+1)%4] = (dp[(i-1)%4]&&two)||(dp[(i-2)%4]&&three);
        }
        return dp[n%4];
    }
}