【华为机试】70. 爬楼梯-EW帮帮网

70. 爬楼梯

描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶

示例 2

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

提示

1 <= n <= 45

解题思路

核心分析

这是一道经典的动态规划入门题目，本质上是斐波那契数列的变形。

问题建模

要到达第n阶楼梯，可以从两个位置到达：

从第(n-1)阶爬1步
从第(n-2)阶爬2步

因此：f(n) = f(n-1) + f(n-2)

这正是斐波那契数列的递推关系！

算法实现

方法1：动态规划（标准解法）

状态定义：

dp[i] 表示到达第i阶楼梯的方法数
dp[i] = dp[i-1] + dp[i-2]

边界条件：

dp[1] = 1（只有一种方法：爬1步）
dp[2] = 2（两种方法：1+1 或 2）

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    
    return dp[n]
}

时间复杂度：O(n)
空间复杂度：O(n)

方法2：空间优化动态规划（最优解）

由于状态转移只依赖前两个状态，可以用两个变量代替数组。

func climbStairsOptimized(n int) int {
    if n <= 2 {
        return n
    }
    
    prev2 := 1  // f(1)
    prev1 := 2  // f(2)
    
    for i := 3; i <= n; i++ {
        curr := prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    
    return prev1
}

时间复杂度：O(n)
空间复杂度：O(1)

方法3：递归 + 记忆化

使用递归思路，配合记忆化避免重复计算。

func climbStairsMemo(n int) int {
    memo := make(map[int]int)
    return climbStairsMemoHelper(n, memo)
}

func climbStairsMemoHelper(n int, memo map[int]int) int {
    if n <= 2 {
        return n
    }
    
    if val, exists := memo[n]; exists {
        return val
    }
    
    result := climbStairsMemoHelper(n-1, memo) + climbStairsMemoHelper(n-2, memo)
    memo[n] = result
    return result
}

时间复杂度：O(n)
空间复杂度：O(n)

方法4：数学公式（斐波那契通项公式）

使用贝尔纳公式直接计算斐波那契数列第n项。

func climbStairsFormula(n int) int {
    if n <= 2 {
        return n
    }
    
    sqrt5 := math.Sqrt(5)
    phi := (1 + sqrt5) / 2        // 黄金比例
    psi := (1 - sqrt5) / 2        // 共轭黄金比例
    
    // 斐波那契通项公式：F(n) = (φ^n - ψ^n) / √5
    // 但这里是 F(n+1)，因为我们的序列是 f(1)=1, f(2)=2
    result := (math.Pow(phi, float64(n+1)) - math.Pow(psi, float64(n+1))) / sqrt5
    
    return int(math.Round(result))
}

时间复杂度：O(1)
空间复杂度：O(1)

方法5：矩阵快速幂

使用矩阵快速幂计算斐波那契数列，适合处理大数。

func climbStairsMatrix(n int) int {
    if n <= 2 {
        return n
    }
    
    // 转换矩阵: [[1,1],[1,0]]
    base := [][]int{{1, 1}, {1, 0}}
    result := matrixPower(base, n-1)
    
    // result * [F(2), F(1)] = [F(n+1), F(n)]
    return result[0][0]*2 + result[0][1]*1
}

func matrixPower(matrix [][]int, n int) [][]int {
    size := len(matrix)
    result := make([][]int, size)
    for i := range result {
        result[i] = make([]int, size)
        result[i][i] = 1  // 单位矩阵
    }
    
    base := make([][]int, size)
    for i := range base {
        base[i] = make([]int, size)
        copy(base[i], matrix[i])
    }
    
    for n > 0 {
        if n&1 == 1 {
            result = matrixMultiply(result, base)
        }
        base = matrixMultiply(base, base)
        n >>= 1
    }
    
    return result
}

func matrixMultiply(a, b [][]int) [][]int {
    size := len(a)
    result := make([][]int, size)
    for i := range result {
        result[i] = make([]int, size)
        for j := 0; j < size; j++ {
            for k := 0; k < size; k++ {
                result[i][j] += a[i][k] * b[k][j]
            }
        }
    }
    return result
}

时间复杂度：O(log n)
空间复杂度：O(1)

复杂度分析

方法	时间复杂度	空间复杂度	优缺点
标准DP	O(n)	O(n)	思路清晰，易理解
空间优化DP	O(n)	O(1)	最实用的解法 ⭐
记忆化递归	O(n)	O(n)	自顶向下，递归栈开销
数学公式	O(1)	O(1)	最快，但有精度问题
矩阵快速幂	O(log n)	O(1)	适合大数，复杂度低

核心要点

斐波那契本质：问题等价于求斐波那契数列第(n+1)项
状态转移：每个状态只依赖前两个状态
空间优化：可以用O(1)空间代替O(n)空间
边界处理：n=1和n=2的特殊情况

数学推导

递推关系证明

设 f(n) 表示到达第n阶楼梯的方法数：

递推关系：

f(n) = f(n-1) + f(n-2)  (n ≥ 3)

初始条件：

f(1) = 1
f(2) = 2

证明：
要到达第n阶，只能从两个位置到达：

从第(n-1)阶爬1步：有 f(n-1) 种方法
从第(n-2)阶爬2步：有 f(n-2) 种方法
总计：f(n-1) + f(n-2) 种方法

斐波那契数列对应关系

爬楼梯序列：1, 2, 3, 5, 8, 13, 21, 34, …
斐波那契序列：1, 1, 2, 3, 5, 8, 13, 21, …

关系：climbStairs(n) = fibonacci(n+1)

通项公式推导

斐波那契数列通项公式：

F(n) = (φ^n - ψ^n) / √5

其中：

φ = (1 + √5) / 2 ≈ 1.618（黄金比例）
ψ = (1 - √5) / 2 ≈ -0.618

因此：

climbStairs(n) = F(n+1) = (φ^(n+1) - ψ^(n+1)) / √5

执行流程图

graph TD
    A[开始: 输入n] --> B{边界判断}
    B -->|n ≤ 2| C[返回n]
    B -->|n > 2| D[选择算法]
    
    D --> E[标准DP]
    D --> F[空间优化DP]
    D --> G[记忆化递归]
    D --> H[数学公式]
    D --> I[矩阵快速幂]
    
    E --> J[创建dp数组]
    F --> K[使用两个变量]
    G --> L[递归+缓存]
    H --> M[黄金比例公式]
    I --> N[矩阵乘法]
    
    J --> O[循环计算f1-fn]
    K --> P[循环更新prev1,prev2]
    L --> Q[递归计算子问题]
    M --> R[直接计算结果]
    N --> S[快速幂计算]
    
    O --> T[返回dp[n]]
    P --> T
    Q --> T
    R --> T
    S --> T
    C --> U[结束]
    T --> U

实际应用

组合计数：计算特定约束下的方案数
路径规划：网格中的路径计数问题
动态规划优化：状态压缩的经典例子
算法面试：考察DP基础的经典题目

扩展变形

步数扩展：如果可以爬1、2、3步怎么办？
限制条件：某些台阶不能踩怎么处理？
成本问题：每步有不同成本，求最小成本
二维扩展：在网格中从左上到右下的路径数

测试用例设计

// 基础测试
n=1 → 1
n=2 → 2
n=3 → 3
n=4 → 5
n=5 → 8

// 边界测试
n=1 → 1 (最小值)
n=45 → 1836311903 (题目限制最大值)

// 斐波那契验证
n=10 → 89
n=20 → 10946
n=30 → 1346269

// 性能测试
大数值测试各算法效率对比

数学性质

黄金比例的美

斐波那契数列中相邻两项的比值趋近于黄金比例φ：

lim(n→∞) F(n+1)/F(n) = φ = (1+√5)/2 ≈ 1.618

奇偶性质

F(n) 为偶数 ⟺ n ≡ 0 (mod 3)

整除性质

gcd(F(m), F(n)) = F(gcd(m, n))

平方和性质

F(1)² + F(2)² + ... + F(n)² = F(n) × F(n+1)

完整题解代码

package main

import (
	"fmt"
	"math"
	"time"
)

// 方法1：动态规划（标准解法）
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}

	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2

	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}

	return dp[n]
}

// 方法2：空间优化动态规划（最优解）
func climbStairsOptimized(n int) int {
	if n <= 2 {
		return n
	}

	prev2 := 1 // f(1)
	prev1 := 2 // f(2)

	for i := 3; i <= n; i++ {
		curr := prev1 + prev2
		prev2 = prev1
		prev1 = curr
	}

	return prev1
}

// 方法3：递归 + 记忆化
func climbStairsMemo(n int) int {
	memo := make(map[int]int)
	return climbStairsMemoHelper(n, memo)
}

func climbStairsMemoHelper(n int, memo map[int]int) int {
	if n <= 2 {
		return n
	}

	if val, exists := memo[n]; exists {
		return val
	}

	result := climbStairsMemoHelper(n-1, memo) + climbStairsMemoHelper(n-2, memo)
	memo[n] = result
	return result
}

// 方法4：数学公式（斐波那契通项公式）
func climbStairsFormula(n int) int {
	if n <= 2 {
		return n
	}

	sqrt5 := math.Sqrt(5)
	phi := (1 + sqrt5) / 2 // 黄金比例
	psi := (1 - sqrt5) / 2 // 共轭黄金比例

	// 斐波那契通项公式：F(n) = (φ^n - ψ^n) / √5
	// 这里是 F(n+1)，因为我们的序列是 f(1)=1, f(2)=2
	result := (math.Pow(phi, float64(n+1)) - math.Pow(psi, float64(n+1))) / sqrt5

	return int(math.Round(result))
}

// 方法5：矩阵快速幂
func climbStairsMatrix(n int) int {
	if n <= 2 {
		return n
	}

	// 标准斐波那契矩阵：[[1,1],[1,0]]
	// F(n) = [[1,1],[1,0]]^(n-1) 的第一行第一列
	// 爬楼梯问题：climbStairs(n) = F(n+1)
	
	base := [][]int{{1, 1}, {1, 0}}
	result := matrixPower(base, n)
	
	// result[0][0] = F(n+1), result[0][1] = F(n)
	return result[0][0]
}

func matrixPower(matrix [][]int, n int) [][]int {
	size := len(matrix)
	result := make([][]int, size)
	for i := range result {
		result[i] = make([]int, size)
		result[i][i] = 1 // 单位矩阵
	}

	base := make([][]int, size)
	for i := range base {
		base[i] = make([]int, size)
		copy(base[i], matrix[i])
	}

	for n > 0 {
		if n&1 == 1 {
			result = matrixMultiply(result, base)
		}
		base = matrixMultiply(base, base)
		n >>= 1
	}

	return result
}

func matrixMultiply(a, b [][]int) [][]int {
	size := len(a)
	result := make([][]int, size)
	for i := range result {
		result[i] = make([]int, size)
		for j := 0; j < size; j++ {
			for k := 0; k < size; k++ {
				result[i][j] += a[i][k] * b[k][j]
			}
		}
	}
	return result
}

// 测试函数
func testClimbingStairs() {
	fmt.Println("=== 70. 爬楼梯测试 ===")

	testCases := []struct {
		name     string
		n        int
		expected int
	}{
		// 基础测试用例
		{"示例1", 2, 2},
		{"示例2", 3, 3},
		{"示例3", 4, 5},
		{"示例4", 5, 8},

		// 边界测试用例
		{"最小值", 1, 1},
		{"小值测试", 6, 13},

		// 斐波那契验证
		{"斐波那契-10", 10, 89},
		{"斐波那契-15", 15, 987},
		{"斐波那契-20", 20, 10946},

		// 中等规模测试
		{"中等规模-25", 25, 121393},
		{"中等规模-30", 30, 1346269},

		// 大规模测试（接近题目限制）
		{"大规模-40", 40, 165580141},
		{"最大值-45", 45, 1836311903},
	}

	methods := []struct {
		name string
		fn   func(int) int
	}{
		{"标准DP", climbStairs},
		{"空间优化DP", climbStairsOptimized},
		{"记忆化递归", climbStairsMemo},
		{"数学公式", climbStairsFormula},
		{"矩阵快速幂", climbStairsMatrix},
	}

	for _, tc := range testCases {
		fmt.Printf("\n测试用例: %s (n=%d)\n", tc.name, tc.n)
		fmt.Printf("期望输出: %d\n", tc.expected)

		for _, method := range methods {
			start := time.Now()
			result := method.fn(tc.n)
			duration := time.Since(start)

			status := "✓"
			if result != tc.expected {
				status = "✗"
			}

			fmt.Printf("%s %s: %d (耗时: %v)\n",
				status, method.name, result, duration)
		}
	}
}

// 性能测试
func performanceTest() {
	fmt.Println("\n=== 性能测试 ===")

	testSizes := []int{10, 20, 30, 40, 45}

	methods := []struct {
		name string
		fn   func(int) int
	}{
		{"标准DP", climbStairs},
		{"空间优化DP", climbStairsOptimized},
		{"记忆化递归", climbStairsMemo},
		{"数学公式", climbStairsFormula},
		{"矩阵快速幂", climbStairsMatrix},
	}

	for _, size := range testSizes {
		fmt.Printf("\n测试规模 n=%d:\n", size)

		for _, method := range methods {
			start := time.Now()
			result := method.fn(size)
			duration := time.Since(start)

			fmt.Printf("%s: 结果=%d, 耗时=%v\n",
				method.name, result, duration)
		}
	}
}

// 算法分析
func algorithmAnalysis() {
	fmt.Println("\n=== 算法分析 ===")

	fmt.Println("时间复杂度:")
	fmt.Println("  • 标准DP: O(n)")
	fmt.Println("  • 空间优化DP: O(n)")
	fmt.Println("  • 记忆化递归: O(n)")
	fmt.Println("  • 数学公式: O(1) ⭐ 最快")
	fmt.Println("  • 矩阵快速幂: O(log n)")

	fmt.Println("\n空间复杂度:")
	fmt.Println("  • 标准DP: O(n)")
	fmt.Println("  • 空间优化DP: O(1) ⭐ 最优实用")
	fmt.Println("  • 记忆化递归: O(n)")
	fmt.Println("  • 数学公式: O(1)")
	fmt.Println("  • 矩阵快速幂: O(1)")

	fmt.Println("\n核心思想:")
	fmt.Println("  1. 斐波那契数列本质：f(n) = f(n-1) + f(n-2)")
	fmt.Println("  2. 状态转移：到达第n阶只能从n-1或n-2阶到达")
	fmt.Println("  3. 空间优化：只需要保存前两个状态")
	fmt.Println("  4. 数学加速：利用黄金比例直接计算")

	fmt.Println("\n推荐使用:")
	fmt.Println("  • 面试/教学: 空间优化DP（平衡了效率和理解难度）")
	fmt.Println("  • 高性能场景: 数学公式（需要注意浮点精度）")
	fmt.Println("  • 大数场景: 矩阵快速幂（避免精度问题）")
}

// 斐波那契数列分析
func fibonacciAnalysis() {
	fmt.Println("\n=== 斐波那契数列分析 ===")

	fmt.Println("爬楼梯与斐波那契的关系:")
	fmt.Printf("%-10s %-15s %-15s\n", "n", "climbStairs(n)", "fibonacci(n+1)")
	fmt.Println(repeatString("-", 45))

	for i := 1; i <= 10; i++ {
		climb := climbStairsOptimized(i)
		fib := fibonacci(i + 1)
		fmt.Printf("%-10d %-15d %-15d\n", i, climb, fib)
	}

	fmt.Println("\n黄金比例验证:")
	for i := 5; i <= 15; i++ {
		fn := float64(climbStairsOptimized(i))
		fn1 := float64(climbStairsOptimized(i + 1))
		ratio := fn1 / fn
		phi := (1 + math.Sqrt(5)) / 2
		fmt.Printf("F(%d)/F(%d) = %.10f, φ = %.10f, 差值 = %.2e\n",
			i+1, i, ratio, phi, math.Abs(ratio-phi))
	}
}

// 辅助函数：计算斐波那契数列
func fibonacci(n int) int {
	if n <= 2 {
		return 1
	}
	a, b := 1, 1
	for i := 3; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

// 可视化演示
func visualDemo() {
	fmt.Println("\n=== 可视化演示 ===")

	n := 5
	fmt.Printf("示例: n = %d\n", n)

	fmt.Println("\n楼梯示意图:")
	for i := n; i >= 1; i-- {
		spaces := repeatString(" ", (n-i)*2)
		fmt.Printf("%s[%d]\n", spaces, i)
	}
	fmt.Println(repeatString(" ", n*2) + "[0] 起点")

	fmt.Println("\n状态转移过程:")
	fmt.Println("f(1) = 1 (一种方法: 爬1步)")
	fmt.Println("f(2) = 2 (两种方法: 1+1 或 2)")

	for i := 3; i <= n; i++ {
		prev1 := climbStairsOptimized(i - 1)
		prev2 := climbStairsOptimized(i - 2)
		curr := prev1 + prev2
		fmt.Printf("f(%d) = f(%d) + f(%d) = %d + %d = %d\n",
			i, i-1, i-2, prev1, prev2, curr)
	}

	fmt.Printf("\n最终答案: %d种方法\n", climbStairsOptimized(n))
}

// 辅助函数：重复字符串
func repeatString(s string, count int) string {
	if count <= 0 {
		return ""
	}
	result := ""
	for i := 0; i < count; i++ {
		result += s
	}
	return result
}

func main() {
	// 执行所有测试
	testClimbingStairs()
	performanceTest()
	algorithmAnalysis()
	fibonacciAnalysis()
	visualDemo()
}

【华为机试】70. 爬楼梯

文章目录