Pku acm 1163 the Triangle 动态规划题目解题报告(一)

时间:2022-11-20 00:34:57

Pku acm 1163 the Triangle  动态规划题目总结()

题目:http://acm.pku.edu.cn/JudgeOnline/problem?id=1163

对于一个有数字组成的二叉树,求由叶子到根的一条路径,使数字和最大,如:

                                  7

            3           8

                              8   1   0

          2   7   4   4

                          4   5   2   6   5

这个是经典的动态规划,也是最最基础、最最简单的动态规划,典型的多段图。思路就是建立一个数组,由下向上动态规划,保存页子节点到当前节点的最大值,Java核心代码如下:

for(int i=num-2;i>=0;i--){

    for(int j=0;j<=i;j++){

        //该句是整个动态规划的核心

number[i][j]=Math.max(number[i+1][j],number[i+1][j+1])+number[i][j];

    }

}

 

 
带有详细注释的代码可以在http://download.csdn.net/user/china8848/获得