109. 数字三角形
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
样例
比如，给出下列数字三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。
注意事项
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。
解题思路：这个题目跟那个数塔的问题非常相似的，数塔求的是最长路径，而这个问题求的是最短路径。一样的分析，从底向上分析，就每次选取两个子节点中较小的那个。最后顶层的那个节点就是所求的值。
代码：
public class Solution {
/**
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
public int minimumTotal(int[][] triangle) {
// write your code here
if (triangle == null || triangle.length == 0) {
return -1;
}
if (triangle[0] == null || triangle[0].length == 0) {
return -1;
}
int len = triangle.length;
for(int i=len-2;i>=0;i--){
for(int j=0;j<=i;j++){
triangle[i][j] = Math.min(triangle[i+1][j],triangle[i+1][j+1])+triangle[i][j];
}
}
return triangle[0][0];
}
}
其他解题方法：
// version 0: top-down
public class Solution {
/**
* @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;
}
if (triangle[0] == null || triangle[0].length == 0) {
return -1;
}
// state: f[x][y] = minimum path value from 0,0 to x,y
int n = triangle.length;
int[][] f = new int[n][n];
// initialize
f[0][0] = triangle[0][0];
for (int i = 1; i < n; i++) {
f[i][0] = f[i - 1][0] + triangle[i][0];
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
// top down
for (int i = 1; i < n; i++) {
for (int j = 1; j < i; j++) {
f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
}
}
// answer
int best = f[n - 1][0];
for (int i = 1; i < n; i++) {
best = Math.min(best, f[n - 1][i]);
}
return best;
}
}
//Version 1: Bottom-Up
public class Solution {
/**
* @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;
}
if (triangle[0] == null || triangle[0].length == 0) {
return -1;
}
// state: f[x][y] = minimum path value from x,y to bottom
int n = triangle.length;
int[][] f = new int[n][n];
// initialize
for (int i = 0; i < n; i++) {
f[n - 1][i] = triangle[n - 1][i];
}
// bottom up
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
}
}
// answer
return f[0][0];
}
}
//Version 2 : Memorize Search
public class Solution {
private int n;
private int[][] minSum;
private int[][] triangle;
private int search(int x, int y) {
if (x >= n) {
return 0;
}
if (minSum[x][y] != Integer.MAX_VALUE) {
return minSum[x][y];
}
minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1))
+ triangle[x][y];
return minSum[x][y];
}
public int minimumTotal(int[][] triangle) {
if (triangle == null || triangle.length == 0) {
return -1;
}
if (triangle[0] == null || triangle[0].length == 0) {
return -1;
}
this.n = triangle.length;
this.triangle = triangle;
this.minSum = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
minSum[i][j] = Integer.MAX_VALUE;
}
}
return search(0, 0);
}
}
来源：https://www.jiuzhang.com/solution/triangle/ | 
转播
