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 public: bool validPartition(vector vector 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(); }};h5Python/h5 pre # from typing import Listclass 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]

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

  Tisfy：https://letmefly.blog.csdn.net/article/details/136405114