Triangle 数字三角形
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
注意事项
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Notice
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Have you met this question in a real interview? Yes Example Given the following triangle:
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
解题思路
为了找到最小路径和，可以直接用dfs暴力搜索出所有路径，然后打擂台把最小的路径和返回。
Code
public class Solution {
private int[][] triangle;
private int bestMinSum = Integer.MAX_VALUE;
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
this.triangle = triangle;
search(0, 0, 0);
return bestMinSum;
}
// dfs
private void search(int row, int col, int minSum) {
if (row == triangle.length) {
if (minSum < bestMinSum) {
bestMinSum = minSum;
}
return;
}
search(row + 1, col, minSum + triangle[row][col]);
search(row + 1, col + 1, minSum + triangle[row][col]);
}
}
这样做的问题是时间复杂度很高，为O(n^2)，因为对于每一个父节点来说，都有两种路径选择，每一层的计算规模以2的倍数增长。
上面的代码是通过遍历来完成了递归过程，同样我们也可以通过分治的方式来完成递归过程，但是时间复杂度一样，分析方式也一样。
优化
通过上方的方式来搜索结果，最大的问题出在无论某一个节点的父路径是否计算过，每次需要用到时仍然需要重新计算. 为了避免这些重复的计算，我们可以事先把之前计算过的结果保存下来，这样的方式称为记忆化搜索。
public class Solution {
private int[][] triangle;
private int[][] saved;
private int bestMinSum = Integer.MAX_VALUE;
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] triangle) {
if (triangle == null || triangle.length == 0) {
return -1;
}
this.triangle = triangle;
// initialize
// tricky for this problem, row is equal to col
this.saved = new int[triangle.length][triangle.length];
for (int i = 0; i < saved.length; i++) {
for (int j = 0; j < saved[0].length; j++) {
saved[i][j] = Integer.MAX_VALUE;
}
}
search(0, 0);
return saved[0][0];
}
// divide & conquer
private int search(int row, int col) {
if (row == triangle.length) {
return 0;
}
// if calculated, return the value
if (saved[row][col] != Integer.MAX_VALUE) {
return saved[row][col];
}
// update path sum
saved[row][col] = triangle[row][col] +
Math.min(search(row + 1, col), search(row + 1, col + 1));
return saved[row][col];
}
}
通过保存了之前的计算过的路径和，再次用到时就不需要重复计算了。
优化过后的时间复杂度为O(n^2)，即和节点数量的规模一样。空间复杂度也是O(n^2)。
可以看到上面就是用了动态规划的思想，最终通过递归来完成了实现，但是在实际工作中，是要避免使用递归的，因为有可能产生栈溢出，所以下面给出了如何用循环来解决这一题。
public class Solution {
/**
* @param triangle: a list of lists of integers.
* @return: An integer, minimum path sum.
*/
public int minimumTotal(int[][] t) {
if (t == null || t.length == 0) {
return -1;
}
int n = t.length;
int[][] f = new int[n][n];
// initial
f[0][0] = t[0][0];
for (int i = 1; i < n; i++) {
f[i][0] = f[i - 1][0] + t[i][0];
f[i][i] = f[i - 1][i - 1] + t[i][i];
}
// update inner element
for (int i = 2; i < n; i++) {
for (int j = 1; j < i; j++) {
f[i][j] = t[i][j] + Math.min(f[i - 1][j - 1], f[i - 1][j]);
}
}
// search from last row
int min = Integer.MAX_VALUE;
for (int i : f[n - 1]) {
if (i < min) {
min = i;
}
}
return min;
}
}
练习 上面的循环是top-down，可以尝试使用bottom-up来实现这题。
Challenge
O(n) memory.
这一题的challenge是只用O(n)的额外空间，n为三角形的总行数。
优化后代码如下
// TODO
总结
对这种坐标类型的动态规划问题
- 令
f[i]或者f[i][j]为在i或i,j这个位置下满足题意的状态。比如这题f[i][j]为从起点走到这个坐标位置的最小路径和。 - 初始化边界情况。如第一个值
f[0]或者第一行第一列如f[0][col]f[row][0]。 - 找出状态转移方程。f[i][j]如何由之前的状态转变而来。
- 返回答案。答案的位置根据定义的
f来确定。
相关问题列表
- Minimum Path Sum (逻辑基本一样)
- Maximum Product Subarray
- Backpack
- Longest Words
- Insert Interval
- Longest Palindromic Substring
Reference
Leetcode, Lintcode