leetcode

0 class Solution {

1 int8_t dp[100001];

2

3 public:

4 Solution() { memset(dp, 0xFF, sizeof(dp)); }

5 bool validPartition(const vector<int> &nums, int idx = 0) {

6 if (idx == nums.size()) return true;

7 if (idx == nums.size() - 1) return false;

8

9 if (dp[idx] != -1) return dp[idx];

10

11 if (nums[idx] == nums[idx + 1]) {

12 if (validPartition(nums, idx + 2)) return dp[idx] = true;

13 }

14

15 if (idx == nums.size() - 2) return dp[idx] = false;

16

17 if (nums[idx] == nums[idx + 1] && nums[idx] == nums[idx + 2]) {

18 if (validPartition(nums, idx + 3)) return dp[idx] = true;

19 }

20

21 if (nums[idx] + 1 == nums[idx + 1] && nums[idx] + 2 == nums[idx + 2]) {

22 if (validPartition(nums, idx + 3)) return dp[idx] = true;

23 }

24

25 return dp[idx] = false;

26 }

27 };