首页 > 代码库 > 数塔问题
数塔问题
数塔问题
题目:给定一个数塔。其存储形式为例如以下所看到的的下三角矩阵。在此数塔中,从顶部出发,在每一节点能够选择向下走还是向右走,一直走究竟层。请找出一条路径,使路径上的数值和最大。
输入例子(数塔):
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
输出例子(最大路径和):
59
分析:
这是动态规划的入门级题目,思路非常easy,自下向上思考,相邻两个数比較大小。取较大的数加到上一层相应的数上面。这样就能够消掉最以下一层,重复这样,直到剩下最顶层的一个数,就是我们要找的最大值。在这个过程中,路径自然也就出来了,就是由相加得到最大值的各个数组成的。比如:第五层中,19 > 7 ,把 19 加到第四层 2 的位置上,2 就变成了 21 ;7 < 10 。把 10 加到第四层 18 的位置上,18 就变成了 28 ;以此类推。
public class Main { // 5行5列;tower1原始数塔 static int[][] tower1 = { { 9 }, { 12, 15 }, { 10, 6, 8 }, { 2, 18, 9, 5 }, { 19, 7, 10, 4, 16 } }; // tower2求解数组 static int[][] tower2 = { { 9 }, { 12, 15 }, { 10, 6, 8 }, { 2, 18, 9, 5 }, { 19, 7, 10, 4, 16 } }; // 求解路径,0代表向下走,1代表向右下走 static int[][] tower3 = new int[5][5]; public static void main(String[] args) { // 第4层至第1层,求解最大值及路径 for (int i = 3; i >= 0; i--) { for (int j = 0; j <= i; j++) { if (tower2[i + 1][j] > tower2[i + 1][j + 1]) { tower2[i][j] += tower2[i + 1][j]; tower3[i][j] = 0; } else { tower2[i][j] += tower2[i + 1][j + 1]; tower3[i][j] = 1; } } } System.out.println("最大值是:" + tower2[0][0]); // 打印路径 int j = 0;// 列下标 for (int i = 0; i <= 3; i++) { System.out.print(tower1[i][j] + " "); j += tower3[i][j]; } System.out.println(tower1[4][j]); } }
数塔问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。