原題傳送門
思路
這道題在CODEVS上标簽是動态規劃,然而本蒟蒻想了半天也沒想出來(可能是我還是太弱了......),于是打算寫個大爆搜看看能混幾分,于是,20分鐘的時間碼完DFS,交上去,AC??!話說這道題資料這麼不給力的嗎???資料這麼小那還用個什麼DP啊???浪費發際線,然而,動态規劃是絕對要比爆搜快的,如果資料夠大,爆搜是無法AC的,而且畢竟做這道題的本意是練習動态規劃,是以我又想了想動态規劃的思路,最終動态規劃的代碼也做出來了,AC~~~
DFS-Code
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
int i,j,n,MAX=-99999999,a[101][101];
void dfs(int x,int y,int v)
{
int newvalue=v+a[x][y];
if(x==n)
{
if(newvalue>MAX)
MAX=newvalue;
return;
}
dfs(x+1,y,newvalue);
dfs(x+1,y+1,newvalue);
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
dfs(1,1,0);
cout<<MAX;
return 0;
}
DP-Code
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
int i,j,n,MAX=-99999999,a[101][101],dp[101][101];
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
cin>>a[i][j];
}
}
for(i=n;i>=1;i--)
{
for(j=1;j<=i;j++)
{
dp[i][j]=max(dp[i+1][j]+a[i][j],dp[i+1][j+1]+a[i][j]);
}
}
cout<<dp[1][1];
return 0;
}
轉載于:https://www.cnblogs.com/gongdakai/p/11402482.html