問題描述：
原題鏈接
給定一個如下圖所示的數字三角形，從頂部出發，在每一結點可以選擇移動至其左下方的結點或移動至其右下方的結點，一直走到底層，要求找出一條路徑，使路徑上的數字的和最大，
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸入格式
第一行包含整數n，表示數字三角形的層數，
接下來n行，每行包含若干整數，其中第 i 行表示數字三角形第 i 層包含的整數，
輸出格式
輸出一個整數，表示最大的路徑數字和，
資料范圍
1≤n≤500,
?10000≤三角形中的整數≤10000
輸入樣例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出樣例：
30
我的分析：
剛開始接觸動態規劃，個人覺得動態規劃有點遞回的味道，記住每個階段的狀態，下一次情況和上一次的狀態有關，解決狀態規劃需要知道狀態轉化（狀態計算，下一次和和上一次狀態之間的聯系）
典型問題：最大最長子序列，最大值問題，
解決方案：
這個題目可以用下往上找的方式，既可以不用考慮負數，也可以不用像順推一樣考慮邊界帶來種種裂開的問題，用f陣列記錄狀態，
我的代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N =510;
int a[N][N],f[N][N];
int n,m;
int main()
{
cin>>n;
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
cin>>a[i][j];
}
}
//cout<<","<<endl;
for(int i=1;i<=n;++i){
f[n][i]=a[n][i];
}
//cout<<","<<endl;
for(int i=n-1;i>=1;--i){
for(int j=1;j<=i;++j){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
}
}
/*for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
cout<<f[i][j]<<" ";
}
cout<<endl;
}除錯查看*/
cout<<f[1][1]<<endl;
return 0;
}
第二種簡略版只需要一個陣列：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N =510;
int f[N][N];
int n,m;
int main()
{
cin>>n;
//都從1開始，避免思路混亂，以后都這么用嘿嘿，
for(int i=1;i<=n;++i){
for(int j=1;j<=i;++j){
cin>>f[i][j];
}
}
for(int i=n-1;i>=1;--i){
for(int j=1;j<=i;++j){//這個地方回圈的結束要搞清楚，第i行有i個數
f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
}
}
cout<<f[1][1]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248155.html
標籤：其他