70、爬楼梯

动态规划问题：通过把原问题分解成相对简单的子问题的方式来解决复杂问题的方法，体现了以空间换时间的算法思想，这也是其与分治法最大的区别。
动态规划解题思路和方法：求解动态规划问题的思路是定义状态并写出状态转移方程，然后可以采用自顶向下的递归+备忘录方法或者自底向上的填写状态转移表方法。
爬楼梯问题，初始时刻在第0级，默认为只有一种方法。第一级也只有一种方法。因为每次只能爬一级或两级楼梯，所以第n级楼梯只与第n-1级和第n-2级楼梯有关。
即f(n) = f(n-1) + f(n-2)，f(n-1)表示爬到第n-1级楼梯一共多少种方法，然后再爬一级到第n级楼梯。f(n-2)表示爬到第n-2级楼梯一共多少种方法，再爬两级到第n级(注意：若爬一级则到第n-1级，已经包含在了f(n-1)中)。得到了这个递推公式就可以直接写代码了。

//爬楼梯
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int climbStairs(int n) {
    int f[n+1];
    f[0] = f[1] = 1;

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

int main()
{
    int result = climbStairs(3);

    cout<<result<<endl;
    return 0;
}