Triangle

https://leetcode.com/problems/triangle/description/

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Thoughts

把三角形左对齐可以看出当以某元素为末尾时，最短值只由其上方和右斜上方元素决定。

Code

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.size() == 0) {
            return 0;
        }
        int[] f = new int[triangle.size() * (triangle.size() + 1) / 2];

        f[0] = triangle.get(0).get(0);
        if (triangle.size() == 1) {
            return f[0];
        }
        int index = 1;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < triangle.size(); i++) {
            min = Integer.MAX_VALUE;
            for (int j = 0; j < triangle.get(i).size(); j++) {
                f[index] = triangle.get(i).get(j);
                if (j == 0) {
                    f[index] += f[index - i];
                } else if (j == i) {
                    f[index] += f[index - i - 1];
                } else {
                    f[index] += Math.min(f[index - i], f[index - i - 1]); 
                }
                min = Math.min(f[index], min);
                index++;
            }
        }

        return min;
    }
}

Analysis

做题耗时30min

Errors:

1. 返回的是f[n-1]

TC: O(n)

Ver.2

从下往上会简单很多.

F(i, j)表示从底往上到(i,j)的min path sum. 由于i层的只和i + 1层的相关, 因此空间只用O(N).

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] f = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[j] = triangle.get(i).get(j) + Math.min(f[j], f[j + 1]); 
            }    
        }

        return f[0];
    }
}