C++U6-05 - 动态规划算法入门

标签：11 main 05 int U6 C++ long include dp

目标：动态规划

 

 

 

 

 

兔子数列的每一项都是前两项之和，公式为f[n]=f[n−1]+f[n−2] 。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int f[105] , n;
    f[1] = 1;
    f[2] = 1;
    cin >> n;
    for(int i = 3 ; i <= n ; i++){
        f[i] = f[i-1] + f[i-2];    
    }
    cout << f[n];
    return 0;
} 

View Code

 

[钞票问题]

 

 

 

dp[i-1] 再拿 1 张 1 元钞票，则是 i 元，因此：dp[i] = dp[i-1] + 1;
dp[i-5] 再拿 1 张 5 元钞票，则是 i 元，因此：dp[i] = dp[i-5] + 1;
dp[i-11] 再拿 1 张 11 元钞票，则是 i 元，因此：dp[i] = dp[i-11] + 1;
题目要求最少的组合张数，所以只需要对 dp[i-1]+1, dp[i-5]+1, dp[i-11]+1 取最小即可。
状态转移方程：dp[i] = min{ dp[i-1]+1, dp[i-2]+1, dp[i-11]+1 };

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int dp[N];
int main() {
    int c[5] = {1, 5, 11} , m;
    cin >> m ;
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < 3 ; j++){
            if (i >= c[j]) {
                dp[i] = min((dp[i - c[j]] + 1) , dp[i]);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}

View Code

 

[数字金字塔]

 

 

 

根据动态规划思想，从小的问题开始解决，我们从下往上开始计算。当前位置能获得的最大值为，当前值加上下面两数较大的值，可得动态转移方程式:dp[i][j]+=max(dp[i−1][j],dp[i−1][j+1]);

#include<bits/stdc++.h>
using namespace std;int dp[1005][1005];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            cin >> dp[i][j];
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = 1; j <= i; j++){
            dp[i-1][j] += max(dp[i][j] , dp[i][j+1]);
        }
    }
    cout << dp[1][1] << endl;
    return 0;
}

View Code

 

[不同的路径]

 

 

假设能有一种状态 dp[i][j] 表示从 (1, 1) 到达 (i, j) 不同路径的总量。那么 m*n 的网格从 (1, 1) 到达 (m, n) 不同路径的总量，就是
dp[m][n]。根据题意 dp[i][j] 作为一次阶段性终点，它只能：
从上面来：dp[i-1][j] 向下走
从左边来：dp[i][j-1] 向右走
因此： dp[i][j] = dp[i-1][j] + dp[i][j-1];

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

View Code

 

 

[传球游戏]

 

 

 

对于每一个同学接到球的来源可以是前一个同学，也可以是后一个同学，且还需要考虑传球次数，因此可以尝试设计状态：dp[i][j] 表示从 1 号开始传球，总共传递了 j 次，传递到 i 号的种类次数。例如 dp[1][0] 表示从 1 号开始传球传 0 次，到达 1 号。显而易见的 dp[1][0] = 1 。根据传球的来源不同，可以做如下划分：
从小编号传来：dp[i-1][j-1]
从大编号传来：dp[i+1][j-1]
因此 dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1];

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[50][50];
int n, m;
inline int backi(int i) { return i-1<=0? n : i-1; }
inline int nexti(int i) { return i+1>n? 1 : i+1; }
int main() {
    cin >> n >> m;
    dp[1][0] = 1;
    for (int j=1; j<=m; j++) {
        for (int i=1; i<=n; i++) {
            dp[i][j] = dp[backi(i)][j-1] + dp[nexti(i)][j-1];
        }
    } 
    cout << dp[1][m] << endl;
    return 0;
}

View Code

 

标签：11,main,05,int,U6,C++,long,include,dp
From： https://www.cnblogs.com/jayxuan/p/18032871