triangle java_LeetCode Triangle Java版本
题目描述：
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.
题目分析：
我的思路是这样的：先用贪婪算法求出一个局部最优解，然后用深度优先算法去遍历，不断替换最优解。结果超时了。。。
代码如下：
public class Solution {
int minSum = 0;
int tempSum = 0;
int rows = 0;
List> tri;
public void deepSearch(int rowNum, int index){
List rowList = tri.get(rowNum);
tempSum += rowList.get(index);
if(rowNum == rows-1){
if(tempSum < minSum)
minSum = tempSum;
tempSum = tempSum - rowList.get(index);
return;
}
deepSearch(rowNum+1,index);
deepSearch(rowNum+1,index+1);
}
public int minimumTotal(List> triangle) {
rows = triangle.size();
if(rows == 0)
return 0;
int index = 0;
List rowList = triangle.get(0);
minSum += rowList.get(0);
for(int i=1;i
rowList = triangle.get(i);
if(rowList.get(index) <= rowList.get(index+1)){
minSum += rowList.get(index);
}
else{
minSum += rowList.get(index+1);
index = index+1;
}
}
tri = triangle;
deepSearch(0,0);
return minSum;
}
}
这个代码自我感觉写的很糟糕。写起来比较费劲，而且不是最优的解法，而且还超时了。自己太过偷懒，什么问题都想着用递归去解决。
看了别人的解法，用的DP，十分简洁，让我很想记录下来。代码如下：
public class Solution {
public int minimumTotal(List> triangle) {
for(int i = triangle.size() - 2; i >= 0; i--)
for(int j = 0; j <= i; j++)
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
return triangle.get(0).get(0);
}
} 很佩服这样的代码，自己还是差很多啊。。