斐波那契和他的不死兔子🐰

方法1(数字<50):

#include <iostream>
using namespace std;
int fibo(int n){
    if (n == 1 || n == 2){
        return 1;
    }
    return fibo(n-1) + fibo(n-2);
    return 0;
}
int main(){
    int n;
    cin >> n;
    cout << "第" << n << "个月有" << fibo(n) << "只🐰";
    return 0;
}

方法2(数字不限):

#include <iostream>
using namespace std;
long long memo[100];
long long fibo(int n , long long memo[]){
    if (n == 1 || n == 2){
        memo[n] = 1;
        return 1;
    }
    if (memo[n] != 0){
        return memo[n];
    }else{
        memo[n] = fibo(n-1 , memo) + fibo(n-2 , memo);
        return memo[n];
    }
    return 0;
}
int main(){
    int n;
    cin >> n;
    cout << "第" << n << "个月有" << fibo(n,memo) << "只🐰";
    return 0;
}

练习:

【例48.1】 斐波那契数列

方法1：

#include <iostream>
using namespace std;
typedef long long ll;
ll fibo(int n){
    if(n==1) return 0;
    if(n==2) return 1;
    return fibo(n-1)+fibo(n-2);
}
int main(){
    int n;
    cin >> n;
    n --;
    cout << fibo(n);
    return 0;
}

方法2(标准)：

#include <iostream>
using namespace std;
long long memo[100];
long long fibo(long long n , long long memo[]){
    if(n == 1 || n == 2){
        memo[n] = 1;
        return 1;
    }
    if (memo[n] != 0){
        return memo[n];
    }else{
        memo[n] = fibo(n - 1, memo) + fibo(n-2,memo);
        return memo[n];
    }
    return 0;
}
int main(){
    long long n;
    cin >> n; 
    n = n - 1;
    cout << fibo(n,memo) << endl;
    return 0;
}

方法3(标准+严谨)：

#include <iostream>
using namespace std;
typedef long long ll;
long long memo[100] = {0,0,1,1,2};
ll fibo(int n , ll memo[]){
    if (memo[n] == 0){
        memo[n] = fibo(n-1,memo) + fibo(n-2,memo);
    }
    if (n == 2 or n == 1){
        return memo[n];
    }
    return memo[n];
}
int main(){
    int n;
    cin >> n;
    cout << fibo(n,memo);
    return 0;
}

「一本通 6.5 练习 1」Fibonacci

#include <iostream>
using namespace std;
int memo[100];
int fibo(int n , int memo[]){
    if (n == 1){
        memo[n] = 1;
        return memo[n];
    }
    if (n == 0){
        memo[n] = 0;
        return memo[n];
    }
    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;
    cout << fibo(n,memo);
    return 0;
}

银币找零💰

方法一:

#include <iostream>
using namespace std;
int mec(int change){
    if (change==0) return 0;
    if (change<0) return -1;
    int count = 10000;
    if (change >= 5){
        count = min(count,mec(change-5)+1);
    }
    if (change >= 2){
        count = min(count,mec(change-2)+1);
    }
    if (change >= 1){
        count = min(count,mec(change-1)+1);
    }
    return count;
}
int main(){
    int n ;
    cin >> n;
    cout << mec(n);
}

练习:面额是1、2、5，用记忆化递归

方法一(递归)

#include <iostream>
using namespace std;
int memo[10000];
long long cnt = 10000000;
int mec(int change,int memo[]){
    if (change==0) return 0;
    if (change<0) return -1;
    int count = 10000;
    if(memo[change] == 0){
        if (change >= 5){
            count = min(count,mec(change-5,memo)+1);
            memo[change] = count;
        }
        if (change >= 2){
            count = min(count,mec(change-2,memo)+1);
            memo[change] = count;
        }
        if (change >= 1){
            count = min(count,mec(change-1,memo)+1);
            memo[change] = count;
        }
        memo[change];
    }
    return memo[change];
}
int main(){
    int n ;
    cin >> n;
    cout << mec(n,memo);
}

练习

【动态规划法】硬币找零问题

方法一（递归）

#include <cstdio>
#include <iostream>
using namespace std;
int coins[10];
int num = 0;
int memo[20];
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];
    for (int i = 0 ; i < num ; i ++){
        if(change >= coins[i]){
            int tmp = 1 + mec(change - coins[i],memo);
            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(change,memo);
    return 0;
}

方法二(递推)

#include <cstdio>
#include <iostream>
using namespace std;
int coins[10];
int num = 0;
const int MN = 100;
int memo[MN];
void mec(int change,int memo[]){
    memo[0] = 0;
    for (int i = 1 ; i < change ; i++){
        memo[i] = -1;
    }
    for (int k = 1 ; 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;
    int n = 10;
    while (n--){
        cin >> coins[num ++];
        if(getchar()== '\n') break;
    }
    mec(MN,memo);
    cout << memo[change];
    return 0;
}

坐标格子⬛️

无限制条件

#include <iostream>
using namespace std;
const int N = 55;
int dp[N][N];
void go(){
    for (int i = 1 ; i <= N ; i++){
            if(i == 1|| j == 1){
                dp[i][j] = 1;
            }else{
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
}
int main(){
    int n , m;
    cin >> n >> m;
    go();
    cout << dp[n][m];
    return 0;
}

有限制条件

#include <iostream>
using namespace std;
const int N = 55;
int dp[N][N];
void go(){
    for (int i = 1 ; i <= N ; i++){
        for (int j = 1 ; j <= N ;j++){
            if (i%2==0 && j%2==0){
                dp[i][j] = 0;
                continue;
            }
            if(i == 1|| j == 1){
                dp[i][j] = 1;
            }else{
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
}
int main(){
    int n , m;
    cin >> n >> m;
    go();
    cout << dp[n][m];
    return 0;
}

背包问题🎒

#include <iostream>
using namespace std;
int v[4] = {0,1500,3000,2000};
int w[4] = {0,1,4,3};
const int N = 20;
int dp[N][N] = {0};
void go(){
    for (int i = 1 ; i <= 3 ; i ++){
        for (int j = 1 ; j <= 4 ; 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();
    int n , m;
    cin >> n >> m;
    cout << dp[n][m];
    return 0;
}

练习:

【例9.11】01背包问题

#include <bits/stdc++.h>
using namespace std;
int w[35] = {0};
int c[35] = {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 k = m ; k >= w[i] ; --k){
            d1[k] = max(d1[k], c[i] + d1[k-w[i]] );
        }
    }
    cout << d1[m] << endl;
    return 0;
}

【例9.12】完全背包问题