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