如果位置 i 是 valid 的，那么满足条件一并且位置 i-2 是 valid 的，或者满足条件二或条件三并且位置 i-3 是 valid 的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def validPartition(self, nums: List[int]) -> bool:
n = len(nums)
dp = [False] * (n + 1)
dp[0] = True
def isValid(i: int) -> bool:
if i >= 2:
if dp[i - 2]:
if nums[i - 1] == nums[i - 2]:
return True
if i >= 3:
if dp[i - 3]:
if nums[i - 1] == nums[i - 2] == nums[i - 3]:
return True
if nums[i - 1] - nums[i - 2] == nums[i - 2] - nums[i - 3] == 1:
return True
return False
for i in range(1, n + 1):
dp[i] = isValid(i)
return dp[-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public:
bool validPartition(vector<int>& nums) {
int n = nums.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
auto isValid = [&](int i) -> bool {
if (i >= 2) {
if (dp[i - 2]) {
if (nums[i - 1] == nums[i - 2]) {
return true;
}
}
}
if (i >= 3) {
if (dp[i - 3]) {
if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {
return true;
}
if (nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) {
return true;
}
}
}
return false;
};
for (int i = 1; i <= n; ++i) {
dp[i] = isValid(i);
}
return dp[n];
}
};
|