题目描述
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
- 子数组 恰 由
2个相等元素组成，例如，子数组[2,2]。 - 子数组 恰 由
3个相等元素组成，例如，子数组[4,4,4]。 - 子数组 恰 由
3个连续递增元素组成，并且相邻元素之间的差值为1。例如，子数组[3,4,5]，但是子数组[1,3,5]不符合要求。
如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。
思路
这道题是比较标准的划分型 DP，可以参考划分型 DP 笔记阅读。那么在这里，我们应该怎样定义状态呢？
很容易想到定义 dp[i] 为从 0 到 i 的元素是否能被有效划分，用 True 代表可以划分，False 代表不可以划分，是否可以呢？
假设目标数组是 [2,2,4,4,4,5,6]，按照我们的划分方式该怎么做呢？
-
第一轮：
[2]显然不是有效划分，此时dp=[False]； -
第二轮：
[2, 2]是有效划分，但是我们很难利用dp[0]帮助我们构造dp，因为我们没有判断空集的办法。 -
逆向想一下，假设
nums最后两个数相等，那么去掉这两个数，问题变成剩下n-2个数是否能有效划分； -
对于其他情况也是一样的道理。
因此我们可以换一个 dp 想法：dp[0] 代表计算过程中的空集，始终为 True，dp[i+1] 为从 0 到 i 的元素是否能被有效划分，这样我们再使用上面的数组作为例子：
- 最开始的时候
dp=[True]； - 第一轮，
[2]对应的dp=[True, False] - 第二轮，
[2, 2]满足两数相等的状态，dp[2]需要我们判断dp[0]是否可以划分，这样就对上了，此时dp=[True, False, True]； - 依次类推。
那么这样我们就需要判断若干种状态：
dp[i+1] = dp[i-1] and nums[i]==nums[i-1]dp[i+1] = dp[i-2] and nums[i]==nums[i-1]==nums[i-2]dp[i+1] = dp[i-2] and nums[i]==nums[i-1]+1==nums[i-2]+2
这样最终的 dp[n] 为所求。
最终代码：
class Solution:
def validPartition(self, nums: List[int]) -> bool:
l = len(nums)
dp = [True] + [False] * l
for i, num in enumerate(nums):
if (i > 0 and dp[i-1] and num == nums[i-1]) or \
(i > 1 and dp[i-2] and
(num == nums[i-1] == nums[i-2] or
num == nums[i-1]+1 == nums[i-2]+2)):
dp[i+1] = True
return dp[l]