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

花韻仙語

发布时间：2025-12-03 14:56:59

707人浏览过

来源于php中文网

原创

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

本文详细探讨了如何使用动态规划解决经典的爬楼梯问题，即计算孩子以1、2或3步跳跃方式爬上n级台阶的所有可能方法数。文章首先阐述了递归备忘录方法，并着重指出go语言中`map`查找的常见陷阱及正确的备忘录检查机制。随后，文章介绍了更高效的迭代式动态规划解决方案，通过代码示例和详细解释，帮助读者理解两种方法的原理、实现及适用场景，并提供了最佳实践建议。

爬楼梯问题概述

爬楼梯问题是一个经典的动态规划（Dynamic Programming, DP）问题。一个孩子要爬上一个有 n 级台阶的楼梯，每次可以跳 1 步、2 步或 3 步。我们需要实现一个方法来计算孩子爬完楼梯的所有可能方式的数量。

问题分析与递推关系

为了解决这个问题，我们可以将其分解为更小的子问题。假设我们想知道爬到第 n 级台阶有多少种方式。

如果孩子最后一步跳了 1 级，那么他之前一定在第 n-1 级台阶。
如果孩子最后一步跳了 2 级，那么他之前一定在第 n-2 级台阶。
如果孩子最后一步跳了 3 级，那么他之前一定在第 n-3 级台阶。

因此，爬到第 n 级台阶的总方式数等于爬到第 n-1 级、第 n-2 级和第 n-3 级台阶的方式数之和。这构成了我们的递推关系： ways(n) = ways(n-1) + ways(n-2) + ways(n-3)

基本情况（Base Cases）

我们需要定义递归的终止条件：

n ：如果台阶数为负数，说明这种情况是不可能的，返回 0 种方式。
n = 0：如果台阶数为 0，意味着孩子已经到达（或者说不需要爬任何台阶），这算作 1 种方式（即什么都不做）。

递归式动态规划与备忘录（Memoization）

递归式动态规划通过自顶向下的方式解决问题，即从 n 开始，递归地计算子问题。为了避免重复计算，我们使用备忘录（通常是一个哈希表或数组）来存储已计算的子问题结果。

Go 语言实现：递归备忘录方法

以下是使用 Go 语言实现递归备忘录方法的代码：

package main

import "fmt"

// CountWaysDP 使用递归和备忘录计算爬楼梯的方式数
func CountWaysDP(n int, memo map[int]int) int {
  // 基本情况
  if n < 0 {
    return 0
  } else if n == 0 {
    return 1
  }

  // 检查是否已计算过该子问题
  // Go 语言中，访问 map 中不存在的键会返回对应类型的零值（int 为 0）
  // 为了正确判断是否已备忘，需要使用 comma-ok 语法
  if val, ok := memo[n]; ok {
    return val
  }

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

func main() {
  // 初始化备忘录 map
  memo := make(map[int]int)
  n := 10 // 假设有 10 级台阶

  fmt.Printf("爬 %d 级台阶共有 %d 种方式\n", n, CountWaysDP(n, memo))
  // 打印备忘录内容，查看哪些子问题被计算和存储
  // fmt.Println("备忘录内容:", memo)
}

备忘录查找的注意事项

在 Go 语言中，当您访问一个 map 中不存在的键时，map 会返回该值类型的零值。对于 int 类型，零值是 0。这在备忘录模式中可能导致问题：

拍我AI

AI视频生成平台PixVerse的国内版本

下载

原始代码问题：如果使用 else if mm[n] > -1 来检查是否已备忘，当 n 尚未计算时，mm[n] 返回 0。由于 0 > -1 为真，程序会错误地认为该结果已计算并返回 0，导致最终结果错误。
常见修复：一种常见的修复是 else if mm[n] > 0。对于爬楼梯问题，因为任何正数台阶的方式数都大于 0，所以这种检查在当前问题中是有效的。如果 mm[n] 为 0，则表示未计算（或计算结果恰好为 0，但这不适用于此问题）。
最佳实践：最健壮和推荐的方式是使用 Go 语言的 comma-ok 语法 if val, ok := memo[n]; ok。ok 布尔值明确指示键是否存在于 map 中。这避免了零值带来的歧义，无论备忘录中存储的值是正数、负数还是零，都能正确判断。

迭代式动态规划（Bottom-Up）

迭代式动态规划通常采用自底向上的方法，从基本情况开始逐步构建解决方案，直到达到目标问题。这种方法避免了递归的开销，并且通常更易于理解和调试。

Go 语言实现：迭代式方法

我们可以使用一个切片（slice）来存储从 0 到 n 的所有台阶的方式数。

package main

import "fmt"

// CountWaysIterative 使用迭代式动态规划计算爬楼梯的方式数
func CountWaysIterative(n int) int {
  if n < 0 {
    return 0
  }
  if n == 0 {
    return 1
  }

  // dp 数组用于存储到达每个台阶的方式数
  // dp[i] 表示到达第 i 级台阶的方式数
  // 数组大小为 n+1，因为需要存储 dp[0] 到 dp[n]
  dp := make([]int, n+1)

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

  // 填充 dp 数组
  for i := 1; i <= n; i++ {
    // 每次可以跳 1, 2, 3 步
    // dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    // 需要确保 i-k 不小于 0

    // 跳 1 步到达 i
    if i-1 >= 0 {
      dp[i] += dp[i-1]
    }
    // 跳 2 步到达 i
    if i-2 >= 0 {
      dp[i] += dp[i-2]
    }
    // 跳 3 步到达 i
    if i-3 >= 0 {
      dp[i] += dp[i-3]
    }
  }

  return dp[n]
}

func main() {
  n := 10 // 假设有 10 级台阶

  fmt.Printf("爬 %d 级台阶共有 %d 种方式 (迭代式)\n", n, CountWaysIterative(n))

  // 泛化循环步数
  n = 10
  dp := make([]int, n+1)
  dp[0] = 1
  for i := 1; i <= n; i++ {
      for k := 1; k <= 3; k++ { // 循环可能的步数 1, 2, 3
          if i-k >= 0 {
              dp[i] += dp[i-k]
          }
      }
  }
  fmt.Printf("爬 %d 级台阶共有 %d 种方式 (迭代式-泛化步数)\n", n, dp[n])
}