algorithm question runtime comparision

I got a question from Leetcode online judge.

http://discuss.leetcode.com/questions/285/triangle
My solution is
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        return helper(triangle,0,0);
    }
    public int helper(ArrayList<ArrayList<Integer>> triangle, int level, int index){
        if(level == (triangle.size()-1))
            return triangle.get(level).get(index);

        return triangle.get(level).get(index)
            + Math.min(helper(triangle,level+1,index),helper(triangle,level+1,index+1));
    }
}
which is correct but not fast enough to pass the large input test.

the other solution below passes the large input test:
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        ArrayList<Integer> sums = new ArrayList<Integer>();

        for(int i=triangle.size()-1;i>=0;i--){
            for(int j=0;j<=i;j++){
                if(sums.size()==j)
                    sums.add(triangle.get(i).get(j));
                else{
                    sums.set(j,triangle.get(i).get(j)+Math.min(sums.get(j),sums.get(j+1)));
                }
            }
        }
        return sums.get(0);
    }
}
I thought both algorithms are running O(n).
Could someone help out here? I really appreciate it.

第一个不是O(n)

一开始你算helper(0,0)，递归了helper(1,0)和helper(1,1)

helper(1,0)递归helper(2,0)和helper(2,1)

helper(1,1)递归helper(2,1)和helper(2,2)

在第二层你helper(2,1)就算了两遍，下面的overlap只会越来越大。

recurrence写出来也不对：T(n)=2T(n-1)

xutopia 发表于 2013-7-4 01:22
第一个不是O(n)

一开始你算helper(0,0)，递归了helper(1,0)和helper(1,1)

yeah, you are right. T(n) = 2T(n-1) = O(2^n). THX!

这个O(n) space解法应该用的是Dynamic Programming。我看下面有人用的这个解法。