2018-2-2

最容易想到的一種，直接求解，后面會(huì)進(jìn)行優(yōu)化。

#include<iostream> #include<cstring> using namespace std;const int N = 350; int x[N+1][N+1],dp[N+1][N+1]; int res,n;int main(){while (cin>>n){memset(x,0,sizeof(x));memset(dp,0,sizeof(dp));for (int i=1;i<=n;i++){for (int j=1;j<=i;j++){cin>>x[i][j];}}dp[1][1]=x[1][1];for (int i=2;i<=n;i++){for (int j=1;j<=i;j++){dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+x[i][j];}}res=0;for (int j=1;j<=n;j++){res=max(res,dp[n][j]);}cout<<res<<endl;}return 0; }

我們觀察上面的代碼可以看出來(lái)，dp數(shù)組當(dāng)前值只與上一行的dp數(shù)組值有關(guān)，所以我們只要記住上一行的狀態(tài)即可，這里的dp換為一維也是可以的，但是我們存在一個(gè)需要注意的地方，如果j是從小到大的，那么我們的dp[j]就已經(jīng)被上一步更新過(guò)了，就不是我們所需要的上一行的值了，所以這里的y是從大到小的。。。

#include<iostream> #include<cstring> using namespace std;const int N = 350; int x[N+1][N+1],dp[N+1]; int res,n;int main(){while (cin>>n){memset(x,0,sizeof(x));memset(dp,0,sizeof(dp));for (int i=1;i<=n;i++){for (int j=1;j<=i;j++){cin>>x[i][j];}}dp[1]=x[1][1];for (int i=2;i<=n;i++){for (int j=i;j>=1;j--){dp[j]=max(dp[j-1],dp[j])+x[i][j];}}res=0;for (int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res<<endl;}return 0; }

除此之外，我們更容易看出的應(yīng)該是x數(shù)組是沒有必要的，我們不需要對(duì)它進(jìn)行存儲(chǔ)。

#include<iostream> #include<cstring> using namespace std;const int N = 350; int dp[N+1]; int res,n;int main(){while (cin>>n){memset(dp,0,sizeof(dp));for (int i=1;i<=n;i++){for (int j=i;j>=1;j--){int t;cin>>t;dp[j]=max(dp[j-1],dp[j])+t;}}res=0;for (int i=1;i<=n;i++){res=max(res,dp[i]);}cout<<res<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj3176 基础的动态规划算法 挑战程序设计竞赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。