動態規劃走樓梯

    //

    //  main.cpp

    //  動態規劃走樓梯

    //

    //  Created by liujan on 11/18/14.

    //  Copyright (c) 2014 liujan. All rights reserved.

    //

    /* 
     問題描述：一個樓梯有20級, 每次走1級或2級, 從底走到 頂一共有多少種走法? 
     分析： 
     假設從底走到第n級的走法有f(n)種, 走到第n級 有兩個方法, 一個是從第(n-1)級走1步, 
     另一個是從第(n- 2)級走2步, 前者有f(n-1)種方法,

     后者有f(n-2)種方法, 所 以f(n)=f(n-1)+f(n-2), 另外f(0)=1, f(1)=1


 優化： 
 利用動態規劃，將每層樓的走法保存下來，避免重復計算 
 */  

#include <iostream>  
using namespace std;  

int result[100]; //保存到達每個樓梯的走法，為了避免重復計算  

int move(int n){  
    if (result[n] > 0) //如果該樓梯此前求過，則直接返回先前的結果就可以了，避免重復求解  
        return result[n];  
    else{  
        int ans = 0;  
        if (n == 0 || n == 1)  
            ans = 1;  
        else{  
            ans = move(n-1) + move(n-2);  
        }  
        result[n] = ans; //保存該樓層計算結果  
        return ans;  
    }  
}  
int main(int argc, const char * argv[]) {  
    // insert code here...  
    memset(result, 0, sizeof(int) * 100);  
    cout << move(20) << endl;  
    return 0;  
}  </pre>