Provide with a recursive way TIME : O(N) SPACE: O(H)


  • 0
    public int findMinPath2(int[][] triangle) {
            if (triangle == null || triangle.length == 0) {
                return 0;
            }
            int height = triangle.length;
            int[] res = new int[1];
            res[0] = Integer.MAX_VALUE;
            findMinPath2Helper(triangle, 0, 0, height, res);
            return res[0];
        }
        
        public void findMinPath2Helper(int[][] triangle, int row, int col, int height, int[] res) {
            int leftParent = 0;
            int rightParent = 0;
            if (row != 0) {
                leftParent = col == 0 ? Integer.MAX_VALUE : triangle[row - 1][col - 1];
                rightParent = col == triangle[row].length - 1 ? Integer.MAX_VALUE : triangle[row - 1][col];
            }
            triangle[row][col] += Math.min(leftParent, rightParent);
            if (row == height - 1) {
                res[0] = Math.min(res[0], triangle[row][col]);
                return;
            }
            findMinPath2Helper(triangle, row + 1, col, height, res);
            if (col == triangle[row].length - 1) {
                findMinPath2Helper(triangle, row + 1, col + 1, height, res);
            }
        }
    

Log in to reply
 

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