Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
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).
思路：采用自顶向下的思路。其中f[i][j] 表示从0， 0 到x，y 的最短路径。对于f[i][0] 或 (i > 0) 其路径只有f[i - 1][0] 到 f[i][0].对于f[i][i] 或 (i > 0) 其路径只有f[i - 1][i - 1] 到 f[i][i].
对于到达f[i][j] (i > 1, j < i) 的路径有f[i - 1][j - 1], f[i -1][j].
1 public class Solution { 2 /** 3 * @param triangle: a list of lists of integers. 4 * @return: An integer, minimum path sum. 5 */ 6 public int minimumTotal(int[][] triangle) { 7 if (triangle == null || triangle.length == 0) { 8 return -1; 9 } 10 if (triangle[0] == null || triangle[0].length == 0) { 11 return -1; 12 } 13 int n = triangle.length; 14 int[][] f = new int[n][n]; 15 f[0][0] = triangle[0][0]; 16 for (int i = 1; i < n; i++) { 17 f[i][0] = f[i - 1][0] + triangle[i][0]; 18 f[i][i] = f[i - 1][i - 1] + triangle[i][i]; 19 } 20 21 for (int i = 1; i < n; i++) { 22 for (int j = 1; j < i; j++) { 23 f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]; 24 } 25 } 26 int best = f[n - 1][0]; 27 for (int i = 1; i < n; i++) { 28 best = Math.min(best, f[n - 1][i]); 29 } 30 return best; 31 } 32 }
原文：http://www.cnblogs.com/FLAGyuri/p/5335743.html