爬楼梯

动态规划

说明

到第 i 阶的方法数等于前两阶之和；滚动状态节省空间。

分析

到第 n 阶的最后一步只可能来自 n−1 阶或 n−2 阶，因此方法数等于两者之和。初始状态取到第 0 阶的一种空走法，随后滚动更新。

图解推演

第 5 阶的走法按最后一步分成互不重叠的两类：从第 4 阶走 1 步，或从第 3 阶走 2 步。因此 f(5)=5+3=8。f(0)=1 是空路径这一种方案，若错设为 0，整个递推都会少算。

查看图表代码

适用前提与边界

这里每次允许走 1 或 2 阶；允许更多步长时递推式也要随之改变。

示例输入与调用

fmt.Println(Climb(5))

运行输出

8

完整 Go 示例

package main

import "fmt"

func Climb(n int) int {
	a, b := 1, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

func main() {
	fmt.Println(Climb(5))
}