總結(jié)一下這類題型的思路：
每一步所求的最優(yōu)解 = 上一步的最優(yōu)解 + 這一步的情況
1.數(shù)字三角形
主要思路：
1.到達(dá)每一個位置的最大和等于前一步最大和加上這一位置的值，而前一步要么是從左上下來，要么是從右上下來，這樣就將原問題分解了
2.記得初始化dp數(shù)組，不然里面元素初值是不確定的
//數(shù)字三角形
//給定一個三角形，每一個結(jié)點(diǎn)選擇移動至左下或者右下，
//找出一條路徑使路徑上數(shù)字和最大
#include<stdio.h>
int max(int a, int b){
if(a>b){
return a;
}
else
return b;
}
int main(){
int n;
scanf("%d",&n);//輸入三角形行數(shù)
int a[n+1][n+1],i,j;
int dp[n+1][n+1];//記錄動態(tài)變化
for(i=0;i<=n;i++){
for(j=0;j<=n;j++){
dp[i][j]=-1;
}
}
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
scanf("%d",&a[i][j]);
}
}
dp[1][1]=a[1][1];
for(i=2;i<=n;i++){
for(j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j];
}
}
int the_max=0;
for(j=1;j<=n;j++){
if(dp[n][j]>the_max){
the_max=dp[n][j];
}
}
printf("%d",the_max);
return 0;
}2.最低通行費(fèi)
//最低通行費(fèi)
//N*N矩陣，左上角進(jìn)，右下角出，不能斜對角通過，求最小和
#include<stdio.h>
int min(int a, int b){
if(a>b)
return b;
else
return a;
}
int main(){
int N;//矩陣寬度
scanf("%d",&N);
int a[N+1][N+1];
int i,j;
for(i=1;i<=N;i++){
for(j=1;j<=N;j++){
scanf("%d",&a[i][j]);
}
}
int dp[N+1][N+1];//動態(tài)數(shù)組
//初始化 ,求最小值，所以初始化盡可能大
for(i=0;i<=N;i++){
for(j=0;j<=N;j++){
dp[i][j]=10000000;
}
}
//完善初始化（很重要的一步）
//左上角元素
dp[1][1]=a[1][1];
//第一行只能從左邊來
for(j=2;j<=N;j++){
dp[1][j]=dp[1][j-1]+a[1][j];
}
//第一列只能從上面來
for(i=2;i<=N;i++){
dp[i][1]=dp[i-1][1]+a[i][1];
}
//必須在2N-1個時間過去，所以只能從左邊或者上邊過來
for(i=2;i<=N;i++){
for(j=2;j<=N;j++){
dp[i][j]=min(dp[i][j-1],dp[i-1][j])+a[i][j];
}
}
printf("%d",dp[N][N]);
return 0;
}3.方格取數(shù)
主要思路：
1.兩條路線一起走，每次記錄到達(dá)兩個點(diǎn)位置可取最大值，本來是用一個四維數(shù)組dp[i1][j1][i2][j2]，但是我們發(fā)現(xiàn)每次只能往左或者往下走一步，說明每一步橫縱坐標(biāo)的和是相同的，就可以設(shè)一個k表示橫縱坐標(biāo)和，且i1+j1=k,i2+j2=k,用一個三維數(shù)組dp[k][i1][i2]替代四維，而可以降低時間復(fù)雜度（重要思維）
2.每一個坐標(biāo)處的最大值，都等于上一步的最大值加上這一步可以獲得的值，而上一步k-1有四種可能，依次比較即可
注意點(diǎn)：
1.給dp定義和初始化時要注意，從0,0開始賦初值（不然會訪問到無值的地址），并且第三維度的大小是N*2+1
2.三重循環(huán)里的判斷語句防止下標(biāo)越界
3.不用根據(jù)題目意思將遍歷過的地方設(shè)置為0，因?yàn)椴皇且淮涡缘倪^程，這里一步一步只能往右邊或者下面走是不會出現(xiàn)重復(fù)的文章來源：http://www.zghlxwxcb.cn/news/detail-859424.html
4.要注意，當(dāng)兩條路線的兩個點(diǎn)不是同一個點(diǎn)時才能相加，否則會重復(fù)相加文章來源地址http://www.zghlxwxcb.cn/news/detail-859424.html
//方格取數(shù)
//某些放入數(shù)據(jù)，其他為0，兩條路徑，和最大，向下或向右走
/*輸入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
*/
//輸出：67
#include<stdio.h>
int max(int a, int b){
return a > b ? a : b ;
}
int main(){
int N;//方格N*N
scanf("%d",&N);
int np[N+1][N+1];
//初始化
int i,j,k;
for(i=1;i<=N;i++){
for(j=1;j<=N;j++){
np[i][j]=0;
}
}
//放入數(shù)據(jù)
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
while(a!=0 || b!=0 || c!=0){
np[a][b]=c;
scanf("%d %d %d",&a,&b,&c);
}
//dp[k][i1][j1]
//i1+j1=i2+j2=k
int dp[N*2+1][N+1][N+1];
//初始化dp，注意下標(biāo)范圍
for(i=0;i<=N*2;i++){
for(j=0;j<=N;j++){
for(k=0;k<=N;k++){
dp[i][j][k]=0;
}
}
}
dp[2][1][1]=np[1][1];//左上角
int i1,i2;
for(k=2;k<=N*2;k++){
for(i1=1;i1<=N;i1++){
for(i2=1;i2<=N;i2++){
int j1=k-i1;
int j2=k-i2;
//防止下標(biāo)越界
if(j1>=1 && j1<=N && j2>=1 && j2<=N){
int t=np[i1][j1];
if(i2!=i1) t+=np[i2][j2];//防止重復(fù)累加，一個地方只能過一次
//np[i1][j1]=np[i2][j2]=0;
//不能設(shè)為0，因?yàn)楸緛砭褪遣粫貜?fù)走的，如果設(shè)為0會影響其他位置的計(jì)算，導(dǎo)致所求值偏小
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t);
dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t);
}
}
}
}
printf("%d",dp[N*2][N][N]);
return 0;
}到了這里，關(guān)于【C】動態(tài)規(guī)劃 之 多維最大最小路徑和的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
