//  
    //  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;  
    }