poj 动态规划DP - 1163 The Triangle

本文主要是介绍poj 动态规划DP - 1163 The Triangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里有一份DP题目列表点击打开链接，大家想专门刷DP的可以看一下。

这是一道经典的DP题，找出从顶到底和最大的路径和。

我们先记录每个路径点上面的值map[i][j] ，这道题的递推式是

map[i][j] = max(map[i-1][j]+map[i][j],map[i-1][j-1]+map[i][j]); 

当然最边缘的路径只有一条，单独考虑。

# include<stdio.h>
# define MAX 105
# define max(x,y)(x>y ? x:y )
int n;
int map[MAX][MAX];void DP(){int i,j,maxd = 0;for(i=1;i<=n;i++){for(j=1;j<=i;j++){if(j==1)map[i][j] += map[i-1][j];else if(j==i)map[i][j]+= map[i-1][j-1];else map[i][j] = max(map[i-1][j]+map[i][j],map[i-1][j-1]+map[i][j]);}}for(i=1;i<=n;i++) maxd= max(maxd,map[n][i]);printf("%d\n",maxd);
}
int main(){int i,j;scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<=i;j++){scanf("%d",&map[i][j]);}}DP();return 0;
}

这篇关于poj 动态规划DP - 1163 The Triangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---