数字三角形之动态规划法

如下图所示的数字三角形，从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。编写一个程序求出最佳路径上的数字之和。 【使用动态规划法实现】 

 

         7 

       3   8 

     8   1   2 

   2   7   4   4 

4    5   2   6   5 

 

输入

输出

样例输入 Copy

2
1
1 2
3
1
1 2
1 2 3

样例输出 Copy

3
6

提示

#include 
#include
#include
int p[105][105];
int a[105][105];
int n;
int max(int i,int j){if(i>j) return i;else return j;
}int main(){int n;while(~scanf("%d",&n)){int i,j;for(i=0;i=0;i--){for(j=0;j<=i;j++){if(i==n-1){p[i][j]=a[i][j];}else {p[i][j]=a[i][j]+max(p[i+1][j],p[i+1][j+1]);}}} printf("%d\n",p[0][0]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！