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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/check-if-there-is-a-valid-partition-for-the-array
• 标签: 动态规划

解法一: 动态规划

go

func validPartition(nums []int) bool {
  n := len(nums)
  dp := make([]bool, n)
  // 初始化 dp 的前三个状态
  dp[0] = false
  dp[1] = nums[0] == nums[1]
  if n == 2 {
    return dp[1]
  }
  dp[2] = dp[1] && nums[1] == nums[2] || nums[0] == nums[1]-1 && nums[0] == nums[2]-2
  // 从第四个元素元素开始递推
  for i := 3; i < n; i++ {
    if dp[i-2] && nums[i] == nums[i-1] {
      // 1. 两个元素相等
      dp[i] = true
    } else if dp[i-3] && nums[i] == nums[i-1] && nums[i] == nums[i-2] {
      // 2. 三个元素相同
      dp[i] = true
    } else if dp[i-3] && nums[i] == nums[i-1]+1 && nums[i] == nums[i-2]+2 {
      // 3. 三个元素递增
      dp[i] = true
    }
  }
  // 返回最后一个元素状态是否可达
  return dp[n-1]
}