动态规划

动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

爬楼梯

其实是一种数学归纳法.

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 111 级或 222 级台阶。

  1. 当为 1 级台阶： 剩 n-1 个台阶，此情况共有 f(n-1) 种跳法。
  2. 当为 2 级台阶： 剩 n-2 个台阶，此情况共有 f(n-2) 种跳法。 即 f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第 n 项，区别仅在于初始值不同：

青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2. 斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1.

int climbStairs(int n){
    if(n == 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    int p[2] = {1,2};
    for(int i = 3;i <= n;++i)
        p[1 - i%2] = p[0] + p[1];
    if(p[0] > p[1]) return p[0];
    return p[1];
}