动态规划解楼梯问题对比分析

“纵有疾风来，人生不言弃”，这句话送给正在学习Golang的朋友们，也希望在阅读本文《动态规划解楼梯问题：递归与迭代对比》后，能够真的帮助到大家。我也会在后续的文章中，陆续更新Golang相关的技术文章，有好的建议欢迎大家在评论留言，非常感谢！

本文深入探讨了经典的楼梯问题，即计算孩子以1、2或3步跳跃方式登上n级楼梯的所有可能方法数。文章详细介绍了两种动态规划解决方案：带有记忆化的递归方法和底向上迭代方法，并通过Go语言示例代码演示了其实现细节、关键逻辑修正以及性能考量，旨在提供清晰、专业的教程指导。

问题描述

假设一个孩子要跑上一个有 n 级台阶的楼梯，他每次可以跳1步、2步或3步。我们的目标是实现一个方法来计算孩子登上这 n 级台阶总共有多少种不同的方式。这是一个典型的动态规划问题，因为它具有重叠子问题和最优子结构特性。

动态规划方法一：递归与记忆化

动态规划的核心思想是避免重复计算。对于楼梯问题，要到达第 n 级台阶，孩子最后一步可能是从第 n-1 级跳1步，从第 n-2 级跳2步，或者从第 n-3 级跳3步。因此，到达第 n 级台阶的总方式数是到达这三级台阶的方式数之和。

我们可以定义 CountWays(n) 为到达第 n 级台阶的方式数，则有： CountWays(n) = CountWays(n-1) + CountWays(n-2) + CountWays(n-3)

基本情况（Base Cases）：

• 当 n < 0 时，表示无法到达负数台阶，方式数为 0。
• 当 n = 0 时，表示已经到达或无需移动（站在地面），这算作 1 种方式（即不跳）。

为了避免重复计算，我们引入记忆化（Memoization），使用一个映射（map）或数组来存储已经计算过的结果。

Go语言实现及关键修正：

在Go语言中，map 在获取一个不存在的键时，会返回该值类型的零值。对于 int 类型，零值是 0。这一点在实现记忆化时尤为重要。

package main

import "fmt"

// CountWaysDP 使用递归和记忆化计算上楼梯的方式
// n: 目标台阶数
// memo: 用于存储已计算结果的映射
func CountWaysDP(n int, memo map[int]int) int {
    // 基本情况：无法到达负数台阶
    if n < 0 {
        return 0
    }
    // 基本情况：到达第0级台阶（即起始位置），算作1种方式
    if n == 0 {
        return 1
    }

    // 检查是否已经计算过此结果
    // 注意：Go的map在键不存在时返回零值(int为0)。
    // 如果memo[n]为0，我们无法区分是未计算还是计算结果恰好为0。
    // 但在此问题中，合法的方式数总是大于0。
    // 因此，如果memo[n] > 0，则表示已经计算过且结果有效。
    if memo[n] > 0 {
        return memo[n]
    }

    // 递归计算并存储结果
    memo[n] = CountWaysDP(n-1, memo) +
        CountWaysDP(n-2, memo) +
        CountWaysDP(n-3, memo)
    return memo[n]
}

func main() {
    memo := make(map[int]int) // 初始化记忆化映射
    n := 10
    result := CountWaysDP(n, memo)
    fmt.Printf("到达 %d 级台阶共有 %d 种方式。\n", n, result)
    // fmt.Println("记忆化映射内容:", memo) // 可以打印查看记忆化过程
}

注意事项：

• 原始问题中 else if mm[n] > -1 的判断对于 map 在Go中是错误的，因为 map 对不存在的键返回 0，而 0 > -1 为真，会导致对未计算的 n 返回 0。正确的判断应该是 memo[n] > 0（因为方式数不可能为负或零，对于 n > 0 的台阶），或者更严谨地使用 if _, ok := memo[n]; ok 来检查键是否存在，并初始化 map 中的值为一个不可能的哨兵值（如 -1）来区分未计算和计算结果。但对于此问题，memo[n] > 0 足够。
• 对于键是连续整数的动态规划问题，使用切片（slice）作为记忆化存储通常比 map 更高效，因为切片提供了O(1)的索引访问，且内存连续性更好。

动态规划方法二：迭代（底向上）

迭代的动态规划方法通常从基本情况开始，逐步计算到目标问题。这种方法避免了递归调用的开销，通常在性能上更优。

Go语言实现：

package main

import "fmt"

// CountWaysIterative 使用迭代（底向上）方式计算上楼梯的方式
// n: 目标台阶数
func CountWaysIterative(n int) int {
    if n < 0 {
        return 0
    }
    if n == 0 {
        return 1
    }

    // dp[i] 表示到达第 i 级台阶的方式数
    // 需要 n+1 个元素，因为索引从0到n
    dp := make([]int, n+1)

    // 基本情况
    dp[0] = 1 // 到达第0级台阶有1种方式（不跳）

    // 从第1级台阶开始迭代计算
    for i := 1; i <= n; i++ {
        // 每次可以跳1、2或3步
        // dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
        // 需要检查 i-k 是否越界
        if i-1 >= 0 {
            dp[i] += dp[i-1]
        }
        if i-2 >= 0 {
            dp[i] += dp[i-2]
        }
        if i-3 >= 0 {
            dp[i] += dp[i-3]
        }
    }

    return dp[n]
}

func main() {
    n := 10
    result := CountWaysIterative(n)
    fmt.Printf("到达 %d 级台阶共有 %d 种方式。\n", n, result)

    // 另一种迭代实现方式（更紧凑）
    // dp := make([]int, n+1)
    // dp[0] = 1
    // for i := 1; i <= n; i++ {
    //  if i >= 1 {
    //      dp[i] += dp[i-1]
    //  }
    //  if i >= 2 {
    //      dp[i] += dp[i-2]
    //  }
    //  if i >= 3 {
    //      dp[i] += dp[i-3]
    //  }
    // }
    // fmt.Println(dp[n])
}

代码解释：

1. 创建一个切片 dp，大小为 n+1，其中 dp[i] 存储到达第 i 级台阶的方式数。
2. 初始化 dp[0] = 1，表示到达第0级台阶有一种方式。
3. 从 i = 1 循环到 n，计算 dp[i]。
4. 对于每个 i，dp[i] 等于 dp[i-1] + dp[i-2] + dp[i-3]。在累加之前，需要确保 i-k 不会小于 0。例如，当 i=1 时，只能从 dp[0] 累加；当 i=2 时，可以从 dp[1] 和 dp[0] 累加。

总结

楼梯问题是动态规划的经典入门案例，它清晰地展示了如何通过分解问题为重叠子问题并存储中间结果来提高效率。

• 递归与记忆化 方法直观地反映了问题的数学递推关系，但可能存在函数调用栈深度限制和一定的函数调用开销。
• 迭代（底向上） 方法通常更高效，因为它避免了递归开销，且内存访问模式更为连续，尤其适合于键是连续整数的场景。对于此类问题，优先考虑使用切片（slice）而非映射（map）进行记忆化存储，以获得更好的性能。

掌握这两种动态规划的实现方式，对于解决更复杂的组合优化问题至关重要。

本篇关于《动态规划解楼梯问题对比分析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！