120. Triangle (1d)

brute force, DFS, over time limit

recursion n levels, like leetcode 22

choose element's left or right ...generate all possible solutions,

time: O(n^2)

https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/

DFS + memoization

time: O(n^2)

space: O(n^2)

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        Integer[][] memo = new Integer[triangle.size()][triangle.size()]; // use Integer object!
        return divideAndConquer(triangle, 0, 0, memo);
        
    }
    private int divideAndConquer(List<List<Integer>> triangle, int x, int y, Integer[][] memo) {
        if (x == triangle.size()) { // reach last row
            return 0; // return no further ans
        }
        if (memo[x][y] != null) {
            return memo[x][y]; // if has cache, directly return it.
        }
        // do divide and conquer in two kinds of movement
        int move1 = divideAndConquer(triangle, x+1, y, memo); // next row, index y
        int move2 = divideAndConquer(triangle, x+1, y+1, memo); // next row, index y+1
        
        memo[x][y] = Math.min(move1, move2) + triangle.get(x).get(y); // do cache
        
        return memo[x][y];
    }
}

// row index: i
// next row, index i or i+1
/*
[2],
[3,4],
[6,5,7],
[4,1,8,3]
*/

DP - bottom up

i: level 層數 j: element

重複性: problem[i, j] = min( sub(i+1, j), sub(i+1, j+1)) + a[i, j]

state array: f[i, j]

DP 方程：f[i, j] = min( f(i+1, j), f(i+1, j+1)) + a[i, j]

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int dp[][] = new int[n+1][n+1];
        
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j] , dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

from bottom to calculate !

time: O(n^2)

space: O(n)

這裡其實改成只用1d 就達成, 因為不用開到 2d 就可以把結果算出來 (可以參考上面連結）

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // i: j
        // i+1: j, j+1 => select min value
        
        //          (2+9) = 11
        //     (3+6)    (4+6) 
        // (6+1)  (5+1)    (7+3)
        // 4      1       8     3 .from bottom 
        
        int dp[] = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

follow up: use in-memory,

不開 dp[], 直接把

 Math.min(dp[j], dp[j+1])

加到

triangle 上面