动态规划之划分型DP

文章目录 判定能否划分2369.检查数组是否存在有效划分 最优划分

判定能否划分

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

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

思路分析：

灵神思路

class Solution: def validPartition(self, nums: List[int]) -> bool: # 就是通过不断正常的条件判断，就是状态没有那么好定义 # dp[i] 表示 前 i 个能否划分 n = len(nums) dp = [True] + [False]*n for i in range(n): # i>0 表示从第二个元素开始,判断从0到nums[i-2]的情况 if i > 0 and dp[i-1] and nums[i] == nums[i-1] or \ i > 1 and dp[i-2] 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[n] 最优划分