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

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

注意：给定 n 是一个正整数。

解题过程：

假如我们没有头绪 可以先列一下前几个组合 ，发现其中得规律从而构造转移方程顺便我们把初始化条件也整理了一下。

n=1 组合

1.  0->1

n=2 组合

1.  0->1->2
#####
2.  0->2

n=3 组合

1.  0->1->2->3 
2.  0->2->3
#####
3.  0->1->3

n=4 组合

1.  0->1->2->3->4
2.  0->2->3->4
3.  0->1->3->4
#####
4.  0->1->2->4
5.  0->2->4

n=5 组合

1.  0->1->2->3->4->5
2.  0->2->3->4->5
3.  0->1->3->4->5
4.  0->1->2->4->5
5.  0->2  ->4->5
#####
1.  0->1->2->3 ->5
2.  0->2->3->5
3.  0->1->3->5

注意看上面得# 我们可以发现 第n层得组合 可以拆分成两部分得组合。

1.  从n-1 得所有结果中我们直接加一步就到底 n

2. 从 n-2 得所有结果中加2步可以到达n

这里我们假设第n 层得结果数为 Sn

则状态方程为 S_n = S_n-1 + S_n-2   , (n>2)

初始化条件 S₁ = 1 ，S₂=2

动态规划解题代码：

动态规划的解题思路一般是查表法 ，目的就是为了记录前几次的执行结果 从而在当前执行过程中选择其中一个最优的子结果。因为我们状态方程比较简单 Sn只依赖Sn-1 和Sn-2 所以我们只需要记录两个变量就可以了。

func fn3(n int) int {
	if n == 2 {
		return 2
	}
	if n == 1 {
		return 1
	}
	s1, s2 := 1, 2

	for i := 3; i <= n; i++ {
		tmp := s2
		s2 = s1 + s2
		s1 = tmp
	}
	return s2
}