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

发表于 分类于 阅读次数： Waline： 本文字数： 162 阅读时长 ≈ 1 分钟

考点

  • 划分DP

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  static const int maxn = 1e5 + 5;
  bool validPartition(vector<int>& nums) {
    int n = nums.size();
    bool f[maxn];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 2; i <= n; ++i) {
      // 第一种情况
      f[i] |= f[i - 2] && nums[i - 1] == nums[i - 2];
      if (i >= 3) {
        // 第二种情况
        f[i] |= f[i - 3] && nums[i - 1] == nums[i - 2] &&
                nums[i - 2] == nums[i - 3];
        // 第三种情况
        f[i] |= f[i - 3] && nums[i - 1] == nums[i - 2] + 1 &&
                nums[i - 2] == nums[i - 3] + 1;
      }
    }
    return f[n];
  }
};

思路

由于是将原数组划分为多个连续的子数组，以每个点作为子数组的结尾，有且只有题目描述的三种情况，直接DP即可