You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

https://mp.weixin.qq.com/s/0AgJmQNYAKzVOyigXiKQhA, 动态规划入门最好材料，也是该题个人认为最完美的解释，没有之一！ 非常感谢该文章的作者和发给我文章的张春玲老师！

自个代码:

\(O(n)\) time, \(O(1)\) extra space.

// A textbook style question for Dynamic Programming.

// I like it!

int climbStairs(int n) {

	// boundarys

	if (n == 1)	return 1;

	if (n == 2)	return 2;

	// state transfer formula

	int a = 1, b = 2, temp;

	for (int i = 3; i <= n; i++) {

		temp = a + b;

		a = b;

		b = temp;

	}

	return temp;

}