题目描述
给你一个下标从 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]
为所求。
最终代码: