題目

題目鏈接
給你一個下標從 0 開始的整數數組 nums ，你必須將數組劃分為一個或多個 連續 子數組。

如果獲得的這些子數組中每個都能滿足下述條件 之一 ，則可以稱其為數組的一種 有效 劃分：

子數組 恰 由 2 個相等元素組成，例如，子數組 [2,2] 。
子數組 恰 由 3 個相等元素組成，例如，子數組 [4,4,4] 。
子數組 恰 由 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 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

思路

這道題可以使用動態規劃來進行解答。

1. 通過前面（n-2）個元素或者是前面（n-3）個元素來進行判斷整個數組是否存在有效的劃分。如果前面（n-2）個元素存在有效的劃分，并且最后兩個元素是相等的，那么整個數組就存在有效的劃分。亦或是前面的（n-3）個元素存在有效的劃分，最后三個元素相等或者是滿足3個連續遞增元素的要求，數組也可以說明存在有效的劃分。
2. 上面就是動態規劃的基本思路，創建一個長度為（n+1）的數組 dp 來記錄數組 nums 是否存在一個有效的劃分，其中 dp[i] 表示前面 i 個元素所組成的數組是否存在一個可行的劃分。最終計算出來的 dp[n] 就是結果

代碼

class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();if (n == 2) {return nums[1] == nums[0];}vector<int> dp(n + 1, 0);dp[0] = 1;dp[2] = nums[1] == nums[0];for (int i = 3; i < n + 1; ++i) {if (nums[i - 1] == nums[i - 2]) {dp[i] |= dp[i - 2];}if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) {dp[i] |= dp[i - 3];}if (nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) {dp[i] |= dp[i - 3];}}return dp[n];}
};

結果