fibo 常规递归写法

#include <iostream>
using namespace  std;
int fibo(int n ){
    if (n == 1 || n  == 2 ){
        return 1;
    }
    // fibo(n)
    return  fibo(n-1) + fibo(n-2);
}

int main(){
    int n = 40;
    cout << " 第 "<< n << " 个月有兔子数为："  <<  fibo(n);
    return 0;
}

fibo 记忆化递归

#include <iostream>
using namespace  std;
typedef long long ll;

ll memo[100];

ll fibo(int n , ll memo[] ){
    if (n == 1 || n  == 2 ){
        memo[n] = 1;
        return 1;
    }
    // fibo(n)
    if (memo[n] != 0 ) {
        return memo[n];
    }
    else{
        memo[n] = fibo(n-1,memo) + fibo(n-2,memo);
        return  memo[n];
    }
}

int main(){
    int n = 50;
    cout << " 第 "<< n << " 个月有兔子数为："  <<  fibo(n, memo) << endl;
    for(int  m : memo){
        cout << m << " ";
    }
    return 0;
}

建议写法

#include <bits/stdc++.h>
using namespace std;
int memo[100];
int fibo(int n, int memo[]){
    // 递归退出条件 f0, f1
    if(n==0 ){
        memo[n] = 0;
        return memo[n];
    }
    if(n== 1){
        memo[n] = 1;
        return memo[n];
    }
    // 是否已经记忆
    //  n != 0 易错
    if(memo[n] != 0){
        return memo[n];
    }

    memo[n] = fibo(n-1,memo) + fibo(n-2,memo);
    return  memo[n];

}
int main(){
    int n = 5; // n < 10000
    cout << fibo(n,memo) << endl;
    for(int x : memo) cout << x << " ";
    return 0;
}

递推

#include <bits/stdc++.h>
using namespace std;
int memo[105] ;  // 便笺，用来记忆计算后的数值
void fibo(int n , int memo[]){
    // 初始化 初始条件即f0,f1
    memo[0] = 0;  // f0
    memo[1] = 1;  // f1
    for(int i = 2 ; i <n; i ++){
        memo[i] = memo[i-1] + memo[i-2];
    }
}
int main(){
    int n = 6;
    // 递推 数组初始化
    fibo(100,memo); // 跑一遍数据
    for(int x : memo ) cout << x << " ";
    // cout << memo[n];
    return 0;
}

硬币找零

记快化递归

#include <iostream>
#include <algorithm>
using namespace std;
int memo[100];

int go(int change,int memo[]){
    // 退出条件
    if(change == 0) return 0;
    if(change < 0 ) return -1;

    // 搜索 memo，是否已经计算过
    if(memo[change] != 0) return memo[change];
    int minN = 10000;
    // change = 6
    if(change >= 5){
        minN = min(minN , 1 + go(change - 5,memo));
        memo[change] = minN;
    } 
    if(change >= 2){
        minN = min(minN , 1+ go(change - 2,memo));
        memo[change] = minN;
    }
    if(change >= 1){
        minN = min(minN , 1+ go(change - 1,memo));
        memo[change] = minN;
    }
    return memo[change];
}
int main(){
    cout << go(100,memo) << endl;
    for(int x : memo) cout << x << " ";
    return 0 ;
}

递推

#include <iostream>
using namespace std;
//moneyChange
const int N = 100;
int coins[3] = {5,2,1};
int memo[N] = {0};
int coinChange(int amount){
	memo[0]=0;
	for(int i = 1; i < N; i++){
		memo[i] = -1;
	}

	for(int change=1;change<=amount;change++){
		
		for(int j=0;j<3;j++){
			if(coins[j]<=change&&memo[change-coins[j]]!=-1){
			//如果当前金额还未计算或者memo[i]比正在计算的解大，则更新最优解memo[i]
				if(memo[change]==-1||memo[change]>memo[change-coins[j]]+1)
					memo[change]=memo[change-coins[j]]+1;
			}
		}
	}
	return memo[amount];	//返回金额amount的最优解
}	
int main(){
	cout << coinChange(18);
    return 0;
}

记忆式递归（不定数硬币面额）

#include <bits/stdc++.h>
using namespace std;
int coins[10] ; // 硬币面额
int num = 0;    // 硬币数量
int memo[20];  // 记录找零的硬币数，下标对应change

int mec(int change,int memo[]){
    // 递归退出条件
    if(change == 0 ) return 0;
    if(change < 0 ) return -1;
    // 重复内容
    int minN = 1000;  // 当前的最小硬币数
    // 已经被记录，直接返回 
    if(memo[change] != 0) return memo[change];

    // 排除以上情况，开始计算并存入 memo
    // 考虑不同面额产生最优解
    for(int i = 0 ; i < num; i++){
        if(change >= coins[i]){
            //cout << "change:" << coins[i] << endl;
            int tmp = 1 + mec(change - coins[i],memo);
            //cout << "tmp:" << tmp <<endl;
            minN = min(minN , tmp);
        }
        // 更新当前面额最优解
        memo[change] = minN;
    }
    return memo[change];
}

int main(){
    int change;
    cin >> change;
    
    while(1){
        cin >> coins[num ++];
        if(getchar() == '\n') break;
    }

    cout << mec(18,memo) << "个硬币\n";

    // for(int x : coins ) cout << x << " ";
    // cout << endl;
    // for(int x : memo) cout << x << " ";
    // cout << endl;



    return 0;
}

递推(不限硬币面额）

#include <bits/stdc++.h>
using namespace std;
int coins[10] ; // 硬币面额
int num = 0;    // 硬币数量
const int MN = 20;
int memo[MN];  // 记录找零的硬币数，下标对应change

void mec(int change,int memo[]){
    memo[0] = 0 ;
    // 初始化 memo 的状态
    for(int i =  1; i < change; i++){
        memo[i] = -1;
    }
    for(int k = 0 ; k < change ; k++){
        for(int j = 0 ; j < num ; j++){
            if(k >= coins[j]){
                int tmp = 1+ memo[k - coins[j]];
                if(memo[k]==-1 )        // 没有被计算过
                    memo[k]=tmp;
                if(tmp < memo[k])       // 新的兑换方式比当前的更优
					memo[k]=tmp;
            }
            
        }
    }
}

int main(){
    int change;
    cin >> change;
    
    while(1){
        cin >> coins[num ++];
        if(getchar() == '\n') break;
    }
    
    mec(20,memo);
    for(int x : memo) cout << x << " ";
    // cout <<  memo[6];

    return 0;
}

走格子

动态规划（无限制条件）

#include <iostream>
using namespace  std;
const int N = 11;
int dp[N][N];
void go(){
    for(int i = 1 ; i < N;i++){
        for(int j = 1; j < N ; j++){
            if(i== 1 || j == 1) {
                dp[i][j] = 1;
            }else{
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
                //cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
            }
        }
    }
}

int main(){
    go();
    cout << dp[3][3];
    return 0;
}

最小路径和

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int dp[N][N]={0};
int grid[N][N];
void go(int n,int m){
        // dp[0][0] = 0;
    for(int i = 1 ; i <= n; i++){
        dp[i][1] = dp[i-1][1] + grid[i][1];
    }
    for(int j = 1 ; j <= m; j++){
        dp[1][j] = dp[1][j-1] + grid[1][j];
    }
    for(int i = 2 ; i <= n; i++){
        for(int j = 2 ; j <= m ; j++){
            dp[i][j] = min( dp[i-1][j] , dp[i][j-1] ) 
                    + grid[i][j];
        }
    }
}
int main(){
    int n , m ;
    cin >> n >> m;
    for(int i = 1 ; i <= n; i++){
        for(int j = 1 ; j <= m ; j++){
            cin >> grid[i][j];
        }
    }
    go(n,m);
    cout << dp[n][m];

    // for(int i = 1 ; i <= n; i++){
    //     for(int j = 1 ; j <= m ; j++){
    //         printf("dp[%d][%d] = %d \n",i,j,dp[i][j]);
    //     }
    // }




    return 0;
}

背包问题

01 背包

#include <iostream>
using namespace std;

int v[4] = {0,1500,3000,2000};
int w[4] = {0,1   ,4   ,3   };  // 最大值为 4 斤，所以下面的循环为 j<=4
const int N = 20;
int dp[N][N] = {0};

void go(){
    // 初始化 0 行 0 列为 0 ，通过数组定义为全局变量，实现 赋值为 0  
    for(int i = 1; i <=3; i ++ ) { // i: 物品
        for(int j = 1; j <= 4 ; j++){ // j: 容量
            if(j >= w[i]){
                int tmp = v[i] + dp[i-1][j-w[i]];
                dp[i][j] = max(tmp,dp[i-1][j]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
}

int main(){
    go();
    cout << "dp[3][3] : " << dp[3][3] << endl;
    cout << "dp[3][4] : " << dp[3][4] << endl;
    return 0;
}

https://ok.hn.cn/p/T1267

题解：

#include <bits/stdc++.h>
using namespace std;
int w[35] = {0}; // 物品重量
int c[35] = {0}; // 物品价值
int dp[35][205]={0};
int d1[205] = {0};
int main(){
    int m,n;
    cin >> m >> n;
    for(int i = 1 ; i <= n;i++){
        cin >> w[i] >> c[i];
    }
    for(int i = 1 ; i<=n; i++){ //物品 
        for(int j = 1; j <= m ; j++){ // 容量
            if(j >= w[i]){
                dp[i][j] = max(dp[i-1][j], c[i] + dp[i-1][j-w[i]] );
            }else{ // 不偷
                dp[i][j] = dp[i-1][j];
            }
        }
        // 滚动数组
        for(int k = m ; k >= w[i] ; --k){
            // dp[j] = max(dp[j], dp[j-w[i]]+c[i]);
            d1[k] = max(d1[k], c[i] + d1[k-w[i]] );
        }
    }

    // cout << dp[m][n] << endl;
    cout << dp[n][m] << endl;
    cout << d1[m] << endl;
    for(int x : d1) cout << x << " ";

    return 0;
}