70. Climbing Stairs

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?

最基本的动态规划题了。也是斐波拉契数列的例子。

方法一： 递归法，直接做。

int climbStairs(int n) { if (n == 0) return 0; if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n-1) + climbStairs(n-2); }

但leetcode会超时，很正常，这也是在这类子问题大量重叠上为甚么要用dynamic programming而不是divide and conquer 的原因。

方法二：动态规划法

int climbStairs(int n) { if (n == 0) return 0; vector<int> res(n,1); if (n == 1) return 1; if (n == 2) return 2; res[1] = 2; for (int i = 2; i < n; i++) { res[i] = res[i-1] + res[i-2]; } return res[n-1]; }

内存优化解法：

int climbStairs2(int n) { vector<int> res(3); //按斐波拉契构造，加了个1 res[0] = 1; res[1] = 1; for (int i = 2; i <= n; i++) { res[i%3] = res[(i-1)%3] + res[(i-2)%3]; } return res[n%3]; }

或者可以更加直白的用三个变量储存结果，其实就是高中的数学归纳法。

int climbStairs(int n) { if (n < 4) return n; int a = 2, b = 3, c = 5; for (int i = 5; i <= n; i++) { a = c; c = b+c; b = a; } // 保持b, c，得到新的结果存为c, a充当临时变量 return c; }