題目連結:HDU2084
題目思路: 從上往下狀态太多不好處理,那麼我們就從下往上遞推,每一層少一個狀态。
設一個一維數組dp 初始狀态存最下面的那一行
即
第五行
dp[1]=4,dp[2]=5,dp[3]=2,dp[4]=6,dp[5]=5
往上遞推一層 轉移方程為 dp[j]=max(dp[j],dp[j+1])+a[i][j];
那麼對于第4行
dp[1]=max(4,5)+2=7;同理
dp[2]=max(5,2)+7=12;
AC代碼:
/*
2017年9月17日10:43:41
HDU2084
AC
*/
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
const int maxn=110;
int a[maxn][maxn];
int dp[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&a[i][j]);
}
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
dp[i]=a[n][i];
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
dp[j]=max(dp[j],dp[j+1])+a[i][j];
//printf("dp[%d]=%d\n",i,dp[i]);
}
}
printf("%d\n",dp[1]);
/*
test intput
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
printf("%d ",a[i][j]);
}printf("\n");
}
*/
}
return 0;
}