题目描述：
给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。
如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：
- 子数组 恰 由
2 个相等元素组成，例如，子数组 [2,2] 。 - 子数组 恰 由
3 个相等元素组成，例如，子数组 [4,4,4] 。 - 子数组 恰 由
3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。
数据范围：
$2\le nums.len \le 10^5$
题解：
贪心感觉不是很行，贪心的话，遇到多个相等的，不知道是 $2$ 个放一起还是 $3$ 个放一起。
考虑动态规划，可以
需要注意初始条件，可以假设 $dp[0] = true$ ，然后 $dp[1,\cdots n]$ 。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
bool validPartition(vector<int> &nums)
{
int n = nums.size();
vector<int> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; ++i)
{
if (i - 2 >= 0 && nums[i - 1] == nums[i - 1 - 1])
dp[i] |= dp[i - 2];
if (i - 3 >= 0 && nums[i - 1] == nums[i - 1 - 1] && nums[i - 1 - 1] == nums[i - 2 - 1])
dp[i] |= dp[i - 3];
if (i - 3 >= 0 && nums[i - 1] == nums[i - 1 - 1] + 1 && nums[i - 1 - 1] == nums[i - 2 - 1] + 1)
dp[i] |= dp[i - 3];
}
return dp[n];
}
};
|