C++U6-07 – 二维线性动态规划

一维二维动态规划是什么？

一维动态规划和二维动态规划是动态规划算法中的两种重要形式，它们的主要区别在于考虑问题的维度和状态转移的方式。

一维动态规划主要在一个方向上考虑问题，通常用于解决一维状态空间的最优化问题。例如，求解一个数组中每个元素的最小操作次数，或者求解一个数列中每个数字的最大值等。其核心思想是通过存储中间计算结果，避免重复计算，提高算法效率。具体来说，它定义了一个状态数组dp，dp[i]表示到达第i个状态（或第i个元素）时的最优解。然后，通过状态转移方程，逐步推导出最终的结果。

二维动态规划则是一维动态规划的拓展，它在一个平面上做动态规划。也就是说，需要考虑两个维度上的状态转移。例如，背包问题、矩阵链乘法问题等，都需要用到二维动态规划。在二维动态规划中，当前格子的状态往往与左边、上边、左上的格子状态有关。因此，我们需要使用一个二维数组dp来存储状态，dp[i][j]表示到达第i行第j列时的最优解。

总的来说，一维动态规划和二维动态规划的主要区别在于它们处理问题的维度不同，一维只在一个方向上考虑状态转移，而二维则在一个平面上考虑。这使得它们在解决不同类型的问题时具有不同的优势。同时，无论是一维还是二维动态规划，其核心思想都是通过存储中间结果，避免重复计算，从而提高算法效率。

[房屋染色]

 dp数组在每个状态中专业的都是到那个阶段的最优解

用dp[i][0]、dp[i][1]、dp[i][2]表示我正在对第i个房子刷油漆的颜色分别是红色、粉色、绿色时的最小花费
最后我们需要求出dp[n][0]、dp[n][1]、dp[n][2]并找到他们的最小值就是本题的答案。

#include<iostream>
using namespace std;
const int N = 510;
int dp[N][N],cost[N][N];
int main(){
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<3;j++){
            cin >> cost[i][j];
        }
    }
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;
       for(int i = 1;i<=n;i++){
        dp[i][0] = min(dp[i-1][1] + cost[i-1][0],dp[i-1][2] + cost[i-1][0]);
        dp[i][1] = min(dp[i-1][0] + cost[i-1][1],dp[i-1][2] + cost[i-1][1]);
        dp[i][2] = min(dp[i-1][0] + cost[i-1][2],dp[i-1][1] + cost[i-1][2]);
    }
    int ans = min(dp[n][0],min(dp[n][1],dp[n][2]));
    cout << ans << endl;
}

View Code

[字符串种类]

第一种：假设输入的数串为s，如果s[i]和s[i-1]组成的两位数已经大于25,s[i]只能单独被翻译，不能和前一个组合。,以字符s[i] 结尾的方案数 = 以字符s[i-1]结尾的方案数
第二种：如果s[i]和s[i-1]组成的两位数小于等于25,s[i]既可以选择选择单独翻译，也可以和前一个数字合并翻译。以字符s[i] 结尾的方案数 =以s[i-1]字符结尾的方案数+以s[i-2]字符结尾的方案数

#include <bits/stdc++.h>
using namespace std;
int dp[110],s[110];
int main(){
    string a;
    cin>>a;
    int n = a.size();
   //将字符串转化成数字存储到s数组中
    for(int i=0;i<n;i++) s[i+1]=a[i]-'0';
   //0个数字或者1个数字的翻译方案为1
    dp[0]=dp[1]=1;
    for(int i=2;i<=n;i++){
        if(s[i-1]*10+s[i]<=25 && s[i-1]>0){ //相邻两个数合并不超过25
            dp[i]=dp[i-1]+dp[i-2];
        }else{ //超过25
            dp[i]=dp[i-1];
        }
    }
    cout<<dp[n];
    return 0;
}

View Code

[挖地雷]

#include<bits/stdc++.h>
using namespace std;
int a[30],dp[30];//dp[i]表示以i为结尾的最多的地雷数目
int mp[30][30];
int n;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++) 
        cin >> a[i];
    //输入n个点到其他点的连线情况
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin >> mp[i][j];
    }
}

int ans=0;
for(int i = 1;i <= n;i++){
    dp[i] = a[i];
    for(int j = 1;j < i;j++){
        //j能到达i，并且使用走到i的地雷更多
        if(mp[j][i]&&dp[j]+a[i]>dp[i]){
            dp[i]=dp[j]+a[i]; //更新dp[i]
        } 
    }
    //找所有dp[i]的最大值
    if(dp[i]>ans) ans=dp[i];
}
cout << ans;

}

View Code

作业讲解视频：

链接：https://pan.baidu.com/s/1cuStIlI_SNiN510wN5Xncg?pwd=nfsz
提取码：nfsz