Published on

Dynamic Programming 動態規劃

Authors
  • avatar
    Name
    Alan Hu
    Twitter

  • Overlapping Subproblems 重疊子問題 求解過程中，許多 subproblems 可能被重複計算。 DP 透過 cache 這些 subproblems 的結果，來避免重複計算。

    可視為分治法的子集，分治法的主要區別： 動態規劃著重於 subproblems 的重疊性，以便通過 Memoization、Tabulation 來提高效率。

  • Optimal Substructure 最優子結構 一個問題的最優解，可以由其子問題的最優解來構建。

  • Cache

    • Memoization 記憶化 (Top-down)
    • Tabulation 表格化 (Bottom-up)

一般 Recursive

fun fibonacci(n: Int): Int {
    return if (n <= 1) n else fibonacci(n - 1) + fibonacci(n - 2)
}

改用 DP

Tabulation (Bottom-up)

  • 由最小 subproblem (Bottom) 開始，逐漸推到大（Up）。
  • 通常使用迭代。
fun fibonacci(n: Int): Int {
    val dp = IntArray(n + 1)
    dp[0] = 0
    dp[1] = 1
    for (i in 2..n) {
	    dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

改進空間複雜度

fun fibonacci(n: Int): Int {
    val dp = intArrayOf(0, 1)
    for (i in 2..n) {
        val last = dp[1]
        dp[1] = last + dp[0]
        dp[0] = last
    }
    return dp[1]
}

Memoization (Top-down)

  • 直接由原本的 problem 開始，逐漸推到小（down）。
  • 通常使用遞迴。

todo