关键词：重叠着子问题
一、Fibonacci斐波那契数列
图片说明

上图展示了斐波那契数列计算过程中子问题重叠的情况，
为了避免重复子问题的计算，
引入记忆化搜索，记忆化数组将重复计算的值记录下来，
从基础子问题开始，自下而上解决问题： 


using namespace std;
int Fib(int n){
    vector<int> memo(n+1, -1);//从0到n，一共n+1个元素
    memo[0] = 0; //基础子问题
    memo[1] = 1; //基础子问题
    for(int i = 2; i<= n; i++){
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

从小数据量的问题入手，层层递推，计算出大数据量的问题，就是动态规划。

维基百科对于动态规划的定义
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.
Ref: Dynamic programming

也就是说，动态规划一定是具备了以下三个特点：

  1. 把原来的问题分解成了几个相似的子问题。（强调“相似子问题”）
  2. 所有的子问题都只需要解决一次。（强调“只解决一次”）
  3. 储存子问题的解。（强调“储存”）

二、跳台阶

同样使用记忆化搜索的方法，用memo数组记录爬台阶的方法种类



因此有memo[2] = memo[1] + memo[0]


以此类推
图片说明

因此有memo[i] = memo[i-1] + memo[i-2] 
int climbStair(int n){
    vector<int> memo(n+1,-1);//仍然是从0到n，一共n+1个元素
    memo[0] = 1;
    memo[1] = 1;
    for(int i = 2; i <= n; i++){
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

递推公式还是挺迷惑的。。。