001.爬楼梯

• 70.爬楼梯
  • 斐波那契数列
  • 完全背包排列问题

爬楼梯 - 斐波那契数列

func climbStairs(n int) int {
	dp0 := 1
	dp1 := 1
	for i := 1; i < n; i++ {
		dp0, dp1 = dp1, dp0 + dp1
	}
	return dp1
}

爬楼梯 - 完全背包排列问题

func climbStairs(n int) int {
	// 完全背包排列问题
	// 可以解决一次爬任意台阶
	steps := [2]int{ 1, 2 }
 
	// dp[i]: 爬到第 i 级台阶，有 dp[i] 种爬法
	dp := make([]int, n + 1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		for _, step := range steps {
			if i - step >= 0 {
				dp[i] += dp[i - step]
			}
		}
	}
 
	return dp[n]
}