📈 1-D DP

一維狀態的動態規劃。

35 題 · 1 篇導讀

📖 分類導讀

動態規劃將大問題分解為重疊子問題，用記憶化 (Memoization) 或列表法 (Tabulation) 避免重複計算。一維 DP 的狀態只有一個維度。

Notes:

  • 定義狀態和轉移方程式是核心
  • 自頂向下（遞迴 + 記憶化）vs 自底向上（迭代）
  • 如果只依賴前幾個狀態，可以用滾動變數優化空間

DP 的四個核心

判斷一題能不能用 DP、以及怎麼寫，圍繞四件事：

  • 最佳子結構：大問題的最優解，能由子問題的最優解組成。
  • 重疊子問題：同一個子問題會被反覆求解——這正是值得記憶化、把指數降到多項式的原因。沒有重疊就只是普通分治。
  • 狀態定義：dp[i] 到底代表什麼？定義不清楚，後面全錯。
  • 轉移方程：dp[i] 如何由更小的狀態推出？以及基底狀態 (base case) 是什麼。

TIP

好的狀態定義，本質是把等價的情境合併：只保留「影響未來決策的最少資訊」，捨棄無關細節，狀態空間才會夠小。狀態設計得好，轉移自然浮現；設計得臃腫，往往是把不影響未來的東西也塞進了狀態。

從記憶化到列表法

// 自頂向下：遞迴 + 記憶化（貼近「原問題拆子問題」的思路）
fun climb(n: Int, memo: IntArray): Int {
    if (n <= 2) return n
    if (memo[n] != 0) return memo[n]
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo)
    return memo[n]
}

// 自底向上：迭代 + 滾動變數（省去遞迴堆疊與 dp 陣列）
fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    var a = 1; var b = 2
    for (i in 3..n) {
        val c = a + b
        a = b; b = c
    }
    return b
}

本章深入

跨倉庫導讀

📘Maximum Subarray Evolution
#5Longest Palindromic SubstringMedium★★★★★⏱ O(n^2)#70Climbing StairsEasy★★★★★⏱ O(n)#91Decode WaysMedium★★★★★⏱ O(n)#120TriangleMedium★★★★★⏱ O(n^2)#139Word BreakMedium★★★★★⏱ O(n^2 * m)#152Maximum Product SubarrayMedium★★★★★⏱ O(n)#198House RobberMedium★★★★★⏱ O(n)#213House Robber IIMedium★★★★★⏱ O(n)#256Paint HouseMedium★★★★★⏱ O(n)#279Perfect SquaresMedium★★★★★⏱ O(n * sqrt(n))#300Longest Increasing SubsequenceMedium★★★★★⏱ O(n log n)#322Coin ChangeMedium★★★★★⏱ O(amount * coins.size)#343Integer BreakMedium★★★★★⏱ O(1)#354Russian Doll EnvelopesHard★★★★★⏱ O(n log n)#377Combination Sum IVMedium★★★★★⏱ O(target * n)#416Partition Equal Subset SumMedium★★★★★⏱ O(n * target)#472Concatenated WordsHard★★★★★⏱ O(n * L^2)#647Palindromic SubstringsMedium★★★★★⏱ O(n^2)#673Number of Longest Increasing SubsequenceMedium★★★★★⏱ O(n log n)#691Stickers to Spell WordHard★★★★★⏱ O(2^n * m * n)#740Delete And EarnMedium★★★★★⏱ O(n + maxVal)#746Min Cost Climbing StairsEasy★★★★★⏱ O(n)#837New 21 GameMedium★★★★★⏱ O(k + maxPts)#983Minimum Cost For TicketsMedium★★★★★⏱ O(maxDay)#1035Uncrossed LinesMedium★★★★★⏱ O(m * n)#1137N-th Tribonacci NumberEasy★★★★★⏱ O(n)#1359Count all Valid Pickup and Delivery OptionsHard★★★★★⏱ O(n)#1406Stone Game IIIHard★★★★★⏱ O(n)#1626Best Team with no ConflictsMedium★★★★★⏱ O(n log M)#1799Maximize Score after N OperationsHard★★★★★⏱ O(2^(2n) * n^2)#1856Maximum Subarray Min ProductMedium★★★★★⏱ O(n)#1964Find the Longest Valid Obstacle Course at Each PositionHard★★★★★⏱ O(n log n)#2140Solving Questions With BrainpowerMedium★★★★★⏱ O(n)#2369Check if There is a Valid Partition For The ArrayMedium★★★★★⏱ O(n)#2466Count Ways to Build Good StringsMedium★★★★★⏱ O(high)