Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For 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).
Note:
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.
Solution:
1 public class Solution { 2 public int minimumTotal(List<List<Integer>> triangle) { 3 if (triangle == null) 4 return 0; 5 int length = triangle.size(); 6 int dp[] = new int[length]; 7 for (int i = 0; i < length; ++i) { 8 dp[i] = triangle.get(length - 1).get(i); 9 } 10 for (int j = length - 2; j >= 0; --j) { 11 int[] temp = dp.clone(); 12 for (int i = j; i >= 0; --i) { 13 temp[i] = Math.min(dp[i], dp[i + 1]) + triangle.get(j).get(i); 14 } 15 dp = temp.clone(); 16 } 17 return dp[0]; 18 } 19 }
rewrite:
1 public class Solution { 2 public int minimumTotal(List<List<Integer>> triangle) { 3 if (triangle == null) 4 return 0; 5 int length = triangle.size(); 6 int dp[] = new int[length]; 7 for (int i = 0; i < length; ++i) { 8 dp[i] = triangle.get(length - 1).get(i); 9 } 10 for (int j = length - 2; j >= 0; --j) { 11 for (int i = 0; i <=j; ++i) { 12 dp[i] = Math.min(dp[i], dp[i + 1]) + triangle.get(j).get(i); 13 } 14 } 15 return dp[0]; 16 } 17 }
前边儿的代码，在每一层上从后往前算，需要再开一个temp数组来放下一层的dp值；
rewrite后的代码，直接在dp上进行操作，节省空间和时间。
原文：http://www.cnblogs.com/Phoebe815/p/4059221.html