22. 动态规划-自顶向下法

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

动态规划（Dynamic Programming）的核心思想是将复杂问题分解为重复的子问题。自顶向下法（Top-Down）通常结合递归与备忘录（Memoization），这种方法也被称为“记忆化搜索”。

算法模板 (以斐波那契数列为例)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun solve(n: Int): Int {
    // 1. 初始化备忘录，通常设为 -1 或 null 表示未计算
    val memo = IntArray(n + 1) { -1 }
    return dp(n, memo)
}

private fun dp(n: Int, memo: IntArray): Int {
    // 2. 终止条件 / 基础情况 (Base Case)
    if (n == 0 || n == 1) return n
    
    // 3. 检查备忘录：如果已经计算过，直接返回结果
    if (memo[n] != -1) {
        return memo[n]
    }
    
    // 4. 状态转移：计算并将结果存入备忘录
    // 这里的逻辑根据具体题目而变，如 dp[n] = dp[n-1] + dp[n-2]
    memo[n] = dp(n - 1, memo) + dp(n - 2, memo)
    
    return memo[n]
}

使用说明

  1. 核心逻辑：

    • 递归（自顶向下）：从最终目标出发，逐层分解直到最简单的基础情况。
    • 备忘录（记忆化）：为了避免重复计算（如斐波那契中多次计算同样的 f(n-2)），将结果保存在数组或哈希表中。

  2. 核心优势：

    • 逻辑清晰：比自底向上的迭代（Tabulation）更容易推导出状态转移关系。
    • 按需计算：只计算解决原问题所需要的子问题，而迭代法通常会计算整个表格。

  3. 适用场景：

    • 问题的状态转移方程非常明确。
    • 存在大量重叠子问题。
    • 递归树深度在可控范围内（避免栈溢出）。

  4. 注意点：

    • 初始化：备忘录的初始值必须是一个在该问题结果中不可能出现的值。
    • 栈空间：如果 n 非常大（如超过 10,000），递归可能会引发 StackOverflowError，此时需改用自底向上的迭代法。
    • 状态设计：动态规划最难的是如何定义 dp 函数的含义。
0 - 算法, 0.0 - 算法模版