来自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];
}
```
