[动态规划] 数塔问题

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

题目

给定一个数塔，其存储形式如下图所示：

在此数塔中，从顶部出发，每一个节点可以选择向左走或者向右走，一直走到底部，找出一条路径，使路径数值相加结果最大。

分析

这是一道简单的动态规划题，状态转移是自下向上的，算法思路：

1. 假如路径经过第四层2，第五层一定选19
2. 假如路径经过第四层18，第五层一定选10
3. 假如路径经过第四层9，第五层一定选10
4. 假如路径经过第四层5，第五层一定选16
5. 把第五层选择的数字加到第四层，就可以消去数塔第五层
6. 依此类推，从下往上一层层的消除，只剩第一层，就是路径数值相加的最大值

public static int maxPath(int[][] tower) {int layers = tower.length;for (int i = layers - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {int left = tower[i + 1][j];int right = tower[i + 1][j + 1];if (left > right) tower[i][j] += left;else tower[i][j] += right;}}return tower[0][0];
}// 测试
public static void main(String[] args) {// 二维数组存储数塔结构int[][] tower = {{9},{12, 15},{10, 6, 8},{2, 18, 9, 5},{19, 7, 10, 4, 16}};int result = maxPath(tower);System.out.println(result);
}

 

这篇关于[动态规划] 数塔问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---