【动态规划-划分型 DP】力扣2369. 检查数组是否存在有效划分

server/2024/11/14 16:46:13/

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个连续子数组。

如果获得的这些子数组中每个都能满足下述条件之一，则可以称其为数组的一种有效划分：

子数组恰由 2 个相等元素组成，例如，子数组 [2,2] 。
子数组恰由 3 个相等元素组成，例如，子数组 [4,4,4] 。
子数组恰由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。
如果数组至少存在一种有效划分，返回 true ，否则，返回 false 。

示例 1：
输入：nums = [4,4,4,5,6]
输出：true
解释：数组可以划分成子数组 [4,4] 和 [4,5,6] 。
这是一种有效划分，所以返回 true 。

示例 2：
输入：nums = [1,1,1,2]
输出：false
解释：该数组不存在有效划分。

在这里插入图片描述

动态规划

class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();vector<int> dp(n+1, 0);if(n == 2){return nums[1] == nums[0];}dp[0] = 1;dp[2] = nums[1] == nums[0];for(int i = 3; i < n+1; i++){if(nums[i-1] == nums[i-2]){dp[i] |= dp[i-2];}if(nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]){dp[i] |= dp[i-3];}if(nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1){dp[i] |= dp[i-3];}}return dp[n];}
};

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们仅遍历一次 nums。
时间复杂度：O(n)。数组 dp 消耗 O(n)。

我们定义一个dp，用来储存在前i个元素中，是否有至少一个有效划分。我们在遍历过程中，一旦发现此时最近的几个元素，能够满足三种有效划分情况的一种，我们根据在这几个元素之前是否也存在有效划分，如果存在，那么说明目前至少存在一种有效划分。

最后返回dp[n]即可。

空间优化

class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();if (n == 2) {return nums[1] == nums[0];}// 只需要三个变量来存储之前的状态bool dp0 = true;              // 对应于 dp[i-3]bool dp1 = false;             // 对应于 dp[i-2]bool dp2 = nums[1] == nums[0]; // 对应于 dp[i-1]bool current = false;          // 用于存储 dp[i] 的值for (int i = 3; i <= n; i++) {current = false;if (nums[i - 1] == nums[i - 2]) {current |= dp1;}if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {current |= dp0;}if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) {current |= dp0;}// 更新 dp0, dp1, dp2dp0 = dp1;dp1 = dp2;dp2 = current;}return current;}
};