使用动态规划解决爬楼梯问题：递归与迭代方法详解-Golang-PHP中文网

使用动态规划解决爬楼梯问题：递归与迭代方法详解

聖光之護

发布： 2025-12-03 17:44:03

原创

910人浏览过

使用动态规划解决爬楼梯问题：递归与迭代方法详解

本文深入探讨如何利用动态规划解决经典的爬楼梯问题，即计算孩子以1、2或3步方式爬n级台阶的总方法数。我们将详细介绍递归带备忘录法和迭代法两种实现策略，并通过go语言代码示例，解析各自的原理、实现细节以及常见陷阱，帮助读者掌握动态规划的核心思想与优化实践。

1. 问题描述

经典的爬楼梯问题是动态规划领域的一个入门级但非常重要的案例。假设一个孩子正在爬一个有 n 级台阶的楼梯，他每次可以跳 1 步、2 步或 3 步。我们的目标是实现一个方法，计算出孩子爬完这 n 级台阶总共有多少种不同的方式。

2. 动态规划核心思想

爬楼梯问题具有典型的动态规划特征：

最优子结构： 爬到第 n 级台阶的方法数，可以通过爬到第 n-1、n-2 或 n-3 级台阶的方法数推导出来。
重叠子问题： 在计算 n 级台阶的方法数时，会多次重复计算更低级台阶的方法数。

因此，我们可以使用动态规划的两种主要方法来解决：带备忘录的递归（自顶向下）和迭代（自底向上）。

3. 递归解法：带备忘录（Memoization）

递归解法首先定义了问题的基本递归关系。要到达第 n 级台阶，最后一步可能是：

从 n-1 级跳 1 步
从 n-2 级跳 2 步
从 n-3 级跳 3 步

因此，到达第 n 级台阶的总方法数 f(n) 为 f(n-1) + f(n-2) + f(n-3)。

基本情况（Base Cases）：

当 n < 0 时，无法到达，方法数为 0。
当 n = 0 时，表示已经到达或不需要移动，方法数为 1（即不移动本身算作一种方式）。

为了避免重复计算，我们使用一个映射（map）或数组来存储已计算过的子问题结果，这就是备忘录。

3.1 备忘录的实现细节与常见陷阱

在Go语言中，map 的零值是 nil。当访问一个不存在的键时，它会返回对应值类型的零值。对于 int 类型，零值是 0。这在处理备忘录时可能导致一个陷阱。

考虑以下 Go 语言代码片段：

package main

import "fmt"

// CountWaysDP 使用递归和备忘录计算爬楼梯的方法数
func CountWaysDP(n int, mm map[int]int) int {
  if n < 0 {
    return 0
  } else if n == 0 {
    return 1
  }
  // 错误示范：如果mm[n]为0（表示未计算或计算结果为0），则会误判为已计算
  // else if mm[n] > -1 { 
  //   return mm[n]
  // } 

  // 正确的备忘录检查：
  // 对于本问题，方法数总是非负的。
  // 如果mm[n]的值大于0，则说明该结果已经被计算并存储。
  // 如果我们初始化mm中的值为-1，则可以检查mm[n] != -1。
  // 但如果map中未存储，Go会返回int的零值0。
  // 由于n=0时结果为1，n>0时结果也应大于0，因此mm[n]>0可以作为有效检查。
  if val, ok := mm[n]; ok { // 检查键是否存在，如果存在则直接返回
      return val
  }

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

func main() {
  mm := make(map[int]int)
  fmt.Println("递归带备忘录结果 (n=10):", CountWaysDP(10, mm))
  fmt.Println("备忘录内容:", mm)
}

登录后复制

陷阱分析： 原始代码中 else if mm[n] > -1 的检查是错误的。因为 map 在键不存在时会返回 int 的零值 0。如果 mm[n] 尚未计算，它会返回 0，而 0 是 >-1 的，这会导致函数错误地认为 n 的结果已经被计算过，并返回错误的 0。

修正方法：

课游记AI

AI原生学习产品

查看详情

使用 val, ok := mm[n] 模式： 这是 Go 语言中检查 map 键是否存在的标准且推荐的方式。ok 会是一个布尔值，指示键是否存在。
初始化备忘录为哨兵值： 如果 map 中的值可以为 0 (例如，某些问题中 0 是有效结果)，可以预先用一个不可能的结果（如 -1）填充 map，然后检查 mm[n] != -1。但在本问题中，方法数总是正数（对于 n>=0），所以 mm[n] > 0 也可以作为一种检查已计算结果的方式，前提是 0 仅作为未计算状态的默认值。

上述修正后的代码使用了 val, ok := mm[n] 模式，更加健壮。

4. 迭代解法：自底向上（Bottom-Up）

迭代解法通常更高效，因为它避免了递归调用的开销和潜在的栈溢出问题。它从基本情况开始，逐步计算出更大的子问题。

我们可以使用一个数组（在 Go 中是切片 []int）来存储从 0 到 n 级台阶的方法数。

dp[i] 表示到达第 i 级台阶的方法数。
dp[0] = 1 (到达第 0 级台阶的方法数)。

然后，我们可以通过循环从 i=1 到 n 计算 dp[i]： dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

需要注意的是，当 i-k < 0 时，对应的 dp[i-k] 不应被计入。

4.1 迭代解法的 Go 语言实现

package main

import "fmt"

// CountWaysIterative 使用迭代（自底向上）计算爬楼梯的方法数
func CountWaysIterative(n int) int {
    if n < 0 {
        return 0
    }
    // 创建一个切片来存储从0到n级台阶的方法数
    // 长度为 n+1，索引0到n
    dp := make([]int, n+1)

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

    // 从第1级台阶开始计算到第n级
    for i := 1; i <= n; i++ {
        // 尝试从1步、2步或3步到达当前台阶 i
        for k := 1; k <= 3; k++ {
            // 确保 i-k 不越界
            if i-k >= 0 {
                dp[i] += dp[i-k]
            }
        }
    }
    return dp[n]
}

func main() {
    n := 10
    fmt.Println("迭代解法结果 (n=10):", CountWaysIterative(n))

    // 也可以打印整个dp数组查看中间结果
    // dp := make([]int, n+1)
    // dp[0] = 1
    // for i := 1; i <= n; i++ {
    //     for k := 1; k <= 3; k++ {
    //         if i-k >= 0 {
    //             dp[i] += dp[i-k]
    //         }
    //     }
    // }
    // fmt.Println("迭代计算的DP数组:", dp)
    // fmt.Println("迭代解法结果 (n=10):", dp[n])
}

登录后复制

代码解释：

dp := make([]int, n+1)：初始化一个长度为 n+1 的切片，用于存储 dp[0] 到 dp[n] 的结果。
dp[0] = 1：设置基本情况。
外层循环 for i := 1; i <= n; i++：遍历从第 1 级到第 n 级台阶。
内层循环 for k := 1; k <= 3; k++：尝试从 i-1、i-2 或 i-3 级台阶跳 k 步到达第 i 级。
if i-k >= 0：确保 i-k 是一个有效的台阶索引，避免访问负数索引。
dp[i] += dp[i-k]：将从 i-k 级台阶跳 k 步到达 i 级的方法数累加到 dp[i] 中。

5. 性能分析

无论是递归带备忘录还是迭代解法，它们的时间复杂度和空间复杂度都为 O(n)。

时间复杂度： 两种方法都只需要计算每个子问题一次。对于 n 个台阶，每个台阶的计算都是常数时间（加法操作），因此总时间复杂度为 O(n)。
空间复杂度： 两种方法都需要一个大小为 O(n) 的数据结构（map 或 slice）来存储中间结果。

迭代解法通常在实际运行中略快于递归解法，因为它避免了函数调用的栈开销，并且通常具有更好的缓存局部性。对于非常大的 n 值，迭代解法还可以避免递归深度过大导致的栈溢出问题。

6. 总结与最佳实践

动态规划是解决具有重叠子问题和最优子结构问题的高效方法。对于爬楼梯问题：

递归带备忘录 是一种直观的实现方式，它遵循问题的自然递归定义，通过存储中间结果避免重复计算。需要注意备忘录的正确初始化和检查逻辑，尤其是 Go 语言 map 零值的特性。
迭代（自底向上） 是一种更健壮和通常更高效的实现方式。它从基本情况逐步构建解决方案，避免了递归的开销和潜在的栈溢出。当 n 值较大时，优先考虑迭代解法。

在实际开发中，选择哪种方法取决于具体问题、性能要求以及代码的可读性偏好。对于大多数动态规划问题，理解并能够实现这两种方法是至关重要的。

以上就是使用动态规划解决爬楼梯问题：递归与迭代方法详解的详细内容，更多请关注php中文网其它相关文章！