dp本质是递归

一 斐波那契数列【备忘录】

二 凑零钱问题-【最优子结构】

322. 零钱兑换 解出动规的问题，核心本质是要找出独立的最优子结构 这道题让我意识到dp也不一定需要数组来存。（当然这道题也可以，备忘录只是优化了搜索的一环） 记忆化搜索解法（超时）：

class Solution {

public:
    int coinChange(vector<int>& coins, int amount) {
        return dp(coins,amount);
    }

    int dp(vector<int>& coins,int amount)
    {
        //base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        int res = INT_MAX;
        for(int coin:coins)
        {
            //计算子问题的结果
            int subProblem = dp(coins,amount-coin);
            //子问题无解跳过
            if (subProblem == -1) continue;
            //子问题中选择最优解
            res = min(res,subProblem + 1);
        }
        return res == INT_MAX?-1:res;

    }

};

记忆化搜索带备忘录：

class Solution {
public:
    vector<int> memo;
    int coinChange(vector<int>& coins, int amount) {
        memo = vector<int> (amount + 1, -666);
        return dp(coins,amount);
    }
    int dp(vector<int>& coins,int
    {
        //base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if(memo[amount]!= -666)
            return memo[amount];
        int res = INT_MAX;
        for(int coin:coins)
        {
            //计算子问题的结果
            int subProblem = dp(coins,amount-coin);
            //子问题无解跳过
            if (subProblem == -1) continue;
            //子问题中选择最优解
            res = min(res,subProblem + 1);
        }
        res = (res == INT_MAX)?-1:res;
        memo[amount] = res;
        return res;
    }

};