LeetCode:Climbing Stairs

感觉自己对递归还是不太熟悉：
http://lintcode.com/en/problem/climbing-stairs/

我们先用递归的角度来看看这个题目：

int a =4;

public static int climbStairsRecur(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return climbStairsRecur(n-1) + climbStairsRecur(n-2);
}

首先我们看看： 如果 n=3 的话，我们就需要调用F(2)和F(1),恰好 F(2)=2 and F(1) =1, 所以n=3 的话 F(3) =3
这里相当于把one step 和 two step 看做一个base case (解决这个问题的最小子问题）

当我们只有一步的时候，我们只有一种解法，如果我们是采取两步的策略，那么我们就有两种解法，第一种是直接取一步，第二种是取两步。所以F(2)=2

因为在这里，所有的问题都只是考虑一步和两步的问题。所以只有两种情况。
再次说明：递归的base case 是最小的问题。

Factorial:
public staic int fac(int n) {
if(n=0) return 1;
else return n*fac(n-1);
}

在这里：
base case =1;
假设n =3
那么程序内部的调用是： (这个是从上往下的过程）：
3fac(2) 调用 fac(2)
2fac(1) 调用 fac(1)
1*fac(0) 调用 fac(0) =base case

这个时候fac(0)=1，所以我们算出
1* fac(0)=1;
2* fac(1)=2;
3* fac(2) =6; 这是一个从下往上的调用过程；

但是递归的问题是在于重复计算：
例如这里调用f(2), 就要重新算 f(1) 和 f(0)
调用 f(1)，就要算f(0) 所以有些部分是重复的。

所以在计算使用递归，时间复杂度是： O (2^n)

所以我们可以先把算出来的部分先储存起来：
例如斐波拉契数列：
1 1 2 3 5 8 13 21 34 55...
我们可以把前两位的数先储存起来：

f[i]=f[i-1]+f[i-2];
f[i-1]=f[1];
f[i-2]=f[i-1];

我们动态的把这个子问题 f[i]=f[i-1]+f[i-2]; 不断的存起来就可以计算了。
这里我们看出 时间复杂度是： O(n) ,快了不少。

回到了Climbing Stairs 这一题，我们怎么用动态规划的思想去做： 其实前面已经给出 递归(recursion)的方法，这里我们需要的是如何转换成DP而已，其实就是转换数组形式：因为我们知道

最base 的 case 就是 f(1) == 1 f(2) == 2; 最小的子问题：
然后我们按照斐波拉契数列的形式存储即可：

stairs[i]=stairs[i-1]+stairs[i-2];
假设n =3 , base[0]=1,base[1]=1
那么stairs[2]=2我们就把这个解法已经存到数组里面了可以随时调用。 就不会再重复计算了。

public static int climbStairs(int n) {
// write your code here
int[] b = new int[n+1];
b[0]=1;
b[1]=1;

    for(int i=2;i<b.length;i++){
        b[i]=b[i-1]+b[i-2];
    }
            
    return b[n];
}

虽然这个是非常简单的动态规划问题，但是还是需要我们注意！ 如何选状态方程的问题。