m***n
发帖数: 9 | 1 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).
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList> t,int l,int sum,int i) {
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left
int right=dfs(t,l+1,sum+t.get(l).get(i+1),i+1);
min=right
return min;
//return left
}
}
刚开始我是想用一个global min去记录最小值然后最后返回。可是这个一直没通过一个
test case:[[-1],[2,3],[1,-1,-3]]
它说我输出-4,应该是-1。然后我就查了半天，不知道怎么会输出-4，然后我自己run了
一下给的相同的test input,结果输出的是-1.。。。。搞不懂怎么oj说我输出-4
后来发现根本没必要这个min变量，可以直接return left和right中最小的，然后通过
了小test case.
我没发现有min和没min本质上的不同。
请教各位大神。谢谢 | g****o
发帖数: 547 | 2 leetcode不是每次都重新创建对象
public class Solution {
int min=Integer.MAX_VALUE;
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
min=Integer.MAX_VALUE;//add this line
if(triangle.size()==0) return 0;
return dfs(triangle,1,triangle.get(0).get(0),0);
}
public int dfs(ArrayList> t,int l,int sum,int i) {
if(l==t.size()) return sum;
int left=dfs(t,l+1,sum+t.get(l).get(i),i);
min=left
int right=dfs(t,l+1,sum+t.get(l).get(i+1),i+1);
min=right
return min;
//return left
}
} | E*****m
发帖数: 25615 | 3 你這個時間會超過， 必須用 DP 才行。
【在 g****o 的大作中提到】
: leetcode不是每次都重新创建对象
: public class Solution {
: int min=Integer.MAX_VALUE;
: public int minimumTotal(ArrayList> triangle) {
: // Start typing your Java solution below
: // DO NOT write main() function
: min=Integer.MAX_VALUE;//add this line
: if(triangle.size()==0) return 0;
: return dfs(triangle,1,triangle.get(0).get(0),0);
: }
| E*****m
发帖数: 25615 | 4 DP 很容易寫
public class Solution {
public int minimumTotal(ArrayList> triangle) {
// Start typing your Java solution below
// DO NOT write main() function
int[] sum=new int[triangle.size()];
for (int i=0;i
sum[i]=triangle.get(triangle.size()-1).get(i);
for (int i=triangle.size()-2;i>=0;i--){
ArrayList cur=triangle.get(i);
for (int j=0;j<=i;j++)
sum[j]=cur.get(j)+Math.min(sum[j], sum[j+1]);
}
return sum[0];
}
} | c***d
发帖数: 26 | 5 把 min=Integer.MAX_VALUE;加到minimumTotal开头。
我一般不用instance variable.
【在 m***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.
: 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).
|
|
