給定整數陣列
nums，判斷是否存在一種分割方式，使得每個子陣列滿足以下條件之一：兩個相等元素、三個相等元素、或三個連續遞增元素。
Example:
Input: nums = [4,4,4,5,6] Output: true
Intuition
TIP
線性 DP：對每個位置檢查是否能從前面的合法分割點延伸 2 或 3 個元素的合法子陣列。
dp[i]= 前i個元素是否能合法分割- 對每個位置
i，檢查三種情況能否從合法的dp[i-2]或dp[i-3]延伸 - 三種合法子陣列：
[a, a]、[a, a, a]、[a, a+1, a+2]
Approaches
1. Memoization (Top-Down DP) — O(n) / O(n)
- Idea: 從位置 0 開始遞迴選擇切 2 或切 3，加 memo 快取「從
i開始能否合法分割剩餘」 - Time:
O(n)- 每個狀態只算一次 - Space:
O(n)- memo 陣列 + 遞迴堆疊
class Solution {
fun validPartition(nums: IntArray): Boolean {
val n = nums.size
// memo[i]: -1 未算, 0 false, 1 true
val memo = IntArray(n + 1) { -1 }
fun dp(i: Int): Boolean {
if (i == n) return true
if (memo[i] != -1) return memo[i] == 1
var ok = false
// 切兩個相等
if (i + 1 < n && nums[i] == nums[i + 1] && dp(i + 2)) ok = true
// 切三個相等
if (!ok && i + 2 < n && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2] && dp(i + 3)) ok = true
// 切三個連續遞增
if (!ok && i + 2 < n && nums[i + 1] == nums[i] + 1 && nums[i + 2] == nums[i] + 2 && dp(i + 3)) ok = true
memo[i] = if (ok) 1 else 0
return ok
}
return dp(0)
}
}2. Bottom-Up DP — O(n) / O(n)
- Idea: 依序檢查每個位置能否從前面的合法分割延伸
- Time:
O(n) - Space:
O(n)
class Solution {
fun validPartition(nums: IntArray): Boolean {
val n = nums.size
val dp = BooleanArray(n + 1)
dp[0] = true
for (i in 2..n) {
// 兩個相等
if (nums[i - 1] == nums[i - 2] && dp[i - 2]) {
dp[i] = true
}
if (i >= 3) {
// 三個相等
if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3] && dp[i - 3]) {
dp[i] = true
}
// 三個連續遞增
if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1 && dp[i - 3]) {
dp[i] = true
}
}
}
return dp[n]
}
}⭐ 3. Rolling Variables — O(n) / O(1)
- Idea: 只依賴前三個狀態，用三個布林變數取代陣列
- Time:
O(n) - Space:
O(1)
class Solution {
fun validPartition(nums: IntArray): Boolean {
val n = nums.size
// dp[i] 代表前 i 個元素能否合法分割
// 只需保留 dp[i-1], dp[i-2], dp[i-3]
var d0 = true // dp[i-3] 初始 dp[0]
var d1 = false // dp[i-2] 初始 dp[-1] 無效
var d2 = false // dp[i-1] 初始 dp[0] (不用，因為從 i=2 開始)
// 但需要更小心的初始化
val dp = BooleanArray(n + 1)
dp[0] = true
for (i in 2..n) {
dp[i] = false
if (nums[i - 1] == nums[i - 2] && dp[i - 2]) dp[i] = true
if (i >= 3 && dp[i - 3]) {
if (nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) dp[i] = true
if (nums[i - 1] == nums[i - 2] + 1 && nums[i - 2] == nums[i - 3] + 1) dp[i] = true
}
}
return dp[n]
}
}🔑 Takeaways
- Pattern: 分割型線性 DP — 決定每段的切割點，從前面的合法狀態延伸
- Key trick: 列舉所有合法子陣列的模式（長度 2 和 3），每個位置最多檢查三種情況