LeetCode 2369.检查数组是否存在有效划分：动态规划(DP)

【LetMeFly】2369.检查数组是否存在有效划分：动态规划(DP)

力扣题目链接：https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array/

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

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

1. 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组 恰 由 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
解释：该数组不存在有效划分。

 

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

方法一：动态规划(DP)

使用一个布尔类型的dp数组，其中dp[i + 1]表示“数组nums的从0到i子数组”是否能被划分。

初始值dp[0] = True，其余dp[i] = False。

我们只需要遍历nums数组：

• 若dp[(i + 1) - 2]为True且nums[i] = nums[i - 1]，则nums可在[0, 1, ..., i - 2]的基础上拼接一个[i - 1, i]，因此dp[i + 1] = True。
• 若dp[(i + 1) - 3]为True且nums[i] = nums[i - 1] = nums[i - 2]或nums[i] = nums[i - 1] + 1 = nums[i - 2] + 2，则则nums可在[0, 1, ..., i - 3]的基础上拼接一个[i - 2, i - 1, i]，因此dp[i + 1] = True。

最终返回dp的最后一个元素即为答案。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

优化空间：

1. 可以发现我们至多用到DP数组中的最近3个元素，因此我们可以使用三个变量来“滚动”，这样空间复杂度能变为$O(1)$。
2. 当最近三个DP元素均为False时，该数组将“永无重见天日之时”，可直接返回False。

AC代码

C++

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        vector<bool> dp(nums.size() + 1);
        dp[0] = true;
        for (int i = 0; i < nums.size(); i++) {
            if (i + 1 - 2 >= 0 && dp[i + 1 - 2] && nums[i] == nums[i - 1]) {
                dp[i + 1] = true;
            }
            if (i + 1 - 3 >= 0 && dp[i + 1 - 3] && ((nums[i] == nums[i - 1] && nums[i] == nums[i - 2] || nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2))) {
                dp[i + 1] = true;
            }
        }
        return dp.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Python

# from typing import List

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        dp = [False] * (len(nums) + 1)
        dp[0] = True
        for i in range(len(nums)):
            if i + 1 - 2 >= 0 and dp[i + 1 - 2] and nums[i] == nums[i - 1]:
                dp[i + 1] = True
            if i + 1 - 3 >= 0 and dp[i + 1 - 3] and (nums[i] == nums[i - 1] == nums[i - 2] or nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2):
                dp[i + 1] = True
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/136405114