一列數(shù)字，求問是否可以切割成若干片，使得每一片滿足以下之一：
1.The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
2.The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
3.The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.
DP
1 #2369
2 #Runtime: 817 ms (Beats 85.71%)
3 #Memory: 26.2 MB (Beats 100%)
4
5 class Solution(object):
6 def validPartition(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: bool
10 """
11 dp = [0] * (len(nums) + 1)
12 dp[0] = 1
13 for i in range(1, len(nums)):
14 if i == 1:
15 if nums[i - 1] == nums[i]:
16 dp[i + 1] = 1
17 continue
18 if nums[i] == nums[i - 1]:
19 dp[i + 1] |= dp[i - 1]
20 if nums[i] == nums[i - 1] == nums[i - 2]:
21 dp[i + 1] |= dp[i - 2]
22 if nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2:
23 dp[i + 1] |= dp[i - 2]
24 return dp[-1]