POJ1163
记得第一次遇到这个题目的时候 当时束手无策啊。。
那个时候 脑袋笨笨的 只想着从上向下计算但是结果还不对。。。
后来想到了从下向上的加和,每次都保存最大的结果,思路出来了就
没经过正规的培训。。。 后来知道属于 DP的多段图

思路:
从最下面的开始
取自己下面的两个点中最大的点加到自己的位置上
使每一层的解为最优的解(最小状态最优化)
mapi+=max(mapi+1,mapi+1);

#include<stdio.h>
#include<string.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int map[105][105];
    int n,i,j;
    while(scanf("%d",&n)!=EOF){
        memset(map,0,sizeof(map));
        for(i=0;i<n;i++){
            for(j=0;j<=i;j++){
                scanf("%d",&amp;map[i][j]);
            }
        }
        for(i=n-2;i>=0;i--){
            for(j=0;j<=i;j++){
                map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
                //printf("%3d",map[i][j]);
            }
            //puts("");
        }
        printf("%d\n",map[0][0]);
    }
    return 0;
}
原创文章采用 CC BY-NC-SA 4.0协议 进行许可,转载请著名转自: POJ1163 Triangle DP入门题目

0 评论