Lexi's Leetcode solutions

[leetcode] Triangle

Posted on: November 18, 2013

这题其实和robot一样,每个点取决于从上到自己和从左上角到自己哪个小,但是一变成一维dp就做了好久。主要是因为这个不是取决于头顶和左边了,而是头顶和左上角,于是需要一个临时数组。

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    int res = Integer.MAX_VALUE;
    int[] d = new int[triangle.get(triangle.size() - 1).size()];
    d[0] = triangle.get(0).get(0);
    for (int i = 1; i < triangle.size(); i++) {
        int rowSize = triangle.get(i).size();
        int[] tmp = new int[rowSize];
        for (int j = 0; j < rowSize; j++)
            tmp[j] = d[j];
        for (int j = 0; j < triangle.get(i).size(); j++) {
            int fromAbove = j < rowSize - 1 ? d[j] : Integer.MAX_VALUE;
            int fromUpperLeft = j > 0 ? tmp[j - 1] : Integer.MAX_VALUE;
            d[j] = Math.min(fromAbove, fromUpperLeft) + triangle.get(i).get(j);
        }
    }
    for (int i = 0; i < d.length; i++) {
        res = Math.min(res, d[i]);
    }
    return res;
}
Advertisements
Tags:

1 Response to "[leetcode] Triangle"

If you do it in bottom up way, you don’t need a temp array
public int minimumTotal(List<List> triangle) {
int rows = triangle.size();
int lengths = triangle.get(triangle.size()-1).size();
int[] dp = new int[lengths + 1];
for (int i = rows-1; i >= 0 ; i–) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
}
}
return dp[0];
}
Thank you for your blog, it is very useful

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: