2369.检查数组是否存在有效划分

链接：2369.检查数组是否存在有效划分
难度：Medium
标签：数组、动态规划
简介：给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

题解 1 - python

• 编辑时间：2024-03-01
• 执行用时：125ms
• 内存消耗：30.87MB
• 编程语言：python
• 解法介绍：dp[i]表示以i为节点时是否能够满足要求。

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[0] = False
        dp[1] = nums[0] == nums[1]
        if n == 2: return dp[1]
        dp[2] = nums[0] == nums[1] - 1 == nums[2] - 2 or \
                nums[0] == nums[1] == nums[2]
        for i in range(3, n):
            dp[i] = dp[i - 2] and nums[i] == nums[i - 1] or \
                    dp[i - 3] and nums[i] == nums[i - 1] == nums[i - 2] or \
                    dp[i - 3] and nums[i] == nums[i - 1] + 1 == nums[i - 2] + 2
        return dp[n - 1]