来自labuladong的算法小抄

• 斐波那契数列

  • 递归解决

    int fib(int n){
        if (n<=0) return 0;
        if(n==1 || n==2){
            retrun 1;
        }
        return fib(n-1)+fib(n-2);
    }
    

  • 有记忆 的递归——自上而下

#include <iostream>
//一会要用这个动态数组容器
#include <vector>
using namespace std;

//在备忘录中查找的函数
int helper(vector<int> & memo,int n){
    //如果为新的节点——未被计算过
    if(n >0 && memo[n] == 0){
        memo[n] = helper(memo,n-1) + helper(memo,n-2);
    }
    return memo[n];
}
int fib(int n){
    if (n <= 0) return 0;
    //创建一个备忘录，存储计算过的节点
    vector<int> memo(n+1,0);
    //初始化最简单的节点
    memo[1] = memo[2] = 1;
    //去备忘录中查找
    return helper(memo,n);
}
int main(){
    int n;
    cin >> n;
    cout << fib(n);
}

• 动态规划

//把备忘录创立成一张表
int fib(int n){
    vector<int>memo(n+1,0);
    memo[1] = memo[2] = 1;
    for(int i = 3;i<=n;i++){
    memo[n] = memo[n-1] +memo[n-2];
    }
    return memo[n];
}

• 优化的动态规划—— 递推

//事实上只需要用两个数来记录memo[n-1],mem0[n-2]即可
int fib(int n){
    if (n<2) return 1;
    int prev = 0,curr = 1;
    for(int i = 0;i<n-1;i++){
        //更新
        int sum = prev+curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

• 凑零钱问题

  • 递归解决

  int coinCharge(vector<int>coins,int amount){
      if(amount == 0) return 0;
      int ans = INT_MAX;  //INT_MAX是在limit.h头文件定义的最大整数
      
      for(int coin:coins){    //for的区间遍历，遍历<>容器元素的一种方法
          //如果币的面额比amount大，不能用
          if(coin > amount) continue;
          int subPro = coinCharge(coins,amount-coin);
          //如果子问题无解
          if(subPro == -1) continue;
          ans = min(ans,subPro);
      }
      return (ans==INT_MAX) ? -1:ans;
  

}
```

* 使用备忘录，记录下子问题的最优解

```c++
int helper(vector<int>&coins,int amount,vector<int>&memo){
    if(memo[amount] == -1){
        int ans = INT_MAX;
        for(int coin :coins){
            //硬币面额大于amount
            if(coin > amount) continue;
            int subPro = helper(coins,amount-coin,memo);
            //如果没有解，subPro = -1,是这个子问题helper结束，返回值是-1
            if(subPro == -1) continue;
            //判断这次循环是否要更新节点
            ans = min(ans,subPro+1);
        }
        memo[amount] = (ans==INT_MAX) ? -1:ans;
    }
    return memo[amount];
}
int coinCharge(vector<int>&coins,int amount ){
    if (amount==0) return 0;
    //初始化所有的节点为-1 memo[i]表示凑出i元需要多少硬币
    vector<int>memo(amount+1,-1);
    return helper(coins,amount,memo);
}
```

* 动态规划

```c++
int coinCharge(vector<int>&coins,int amount){
    //用一个永远都不会出现的值初始化
    vector<int>dp(amount+1,amount+1);
    dp[0] = 0;
    for(coin:coins){
        if(coin > amount) continue;
        dp[i] = min(dp[i],dp[i-coin] +1);
    }
    return (dp[amount]== amount+1?-1:dp[amount];
}
```