Top-down DP solution


  • 0
    E

    use an auxiliary 2D array to store the shortest path needed to get to (i, j)

    State Definition: dp[i][j]: the shortest path sum to get to point (i, j)
    Initialization: dp[0][0] = triangle[0][0]
    Transfer Function: dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j] (if j - 1 and j are both inbound)
    Result: minimum value from last row in dp array

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.