2369. Check if There is a Valid Partition For The Array

Check if There is a Valid Partition For The Array

題目描述： 給定一個整數陣列 nums，判斷是否存在一種合法的分割方式，將陣列分成一個或多個子陣列，其中每個子陣列滿足以下其一：

• 恰好 2 個相等的元素
• 恰好 3 個相等的元素
• 恰好 3 個連續遞增的元素（差值為 1）

解題思路： 使用動態規劃：

1. 定義 dp[i] = nums[0..i-1]（前 i 個元素）是否可以合法分割。
2. 轉移條件（對於 dp[i]）：
   • 若 nums[i-1] == nums[i-2] 且 dp[i-2] 為 true → dp[i] = true（2 個相等）
   • 若 i >= 3 且 nums[i-1] == nums[i-2] == nums[i-3] 且 dp[i-3] 為 true → dp[i] = true（3 個相等）
   • 若 i >= 3 且 nums[i-1] == nums[i-2]+1 == nums[i-3]+2 且 dp[i-3] 為 true → dp[i] = true（3 個連續遞增）
3. 基底：dp[0] = true（空陣列可分割）。
4. 答案為 dp[n]。

時間複雜度：O(n) — 單次遍歷陣列。

空間複雜度：O(n) — DP 陣列大小為 n+1。可用滾動變數優化至 O(1)。

滾動變數 O(1) 空間：由於 dp[i] 只依賴 dp[i-2] 和 dp[i-3]，可以用 3 個變數代替整個陣列。

遞迴 + 記憶化 O(n)：自頂向下嘗試從位置 0 開始，每次選擇切出 2 或 3 個元素的子陣列。邏輯直觀但有遞迴開銷。

1. 如果允許的子陣列模式增加（例如 4 個相等或 4 個連續遞增），DP 轉移如何擴展？
2. 如何輸出一種合法的分割方案（而非僅判斷是否存在）？
3. 如果元素可以重新排列後再分割，問題的性質如何改變？