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

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) // 可以打印查看记忆化过程
}

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])
}