DP java solution


  • 0
    M
      public static int minimumTotal(List<List<Integer>> triangle) {
        int row=triangle.size();
        int[][] dp=new int[row][row];
        dp[0][0]=triangle.get(0).get(0);
        for(int i=1;i<row;i++){
            dp[i][0]=dp[i-1][0]+triangle.get(i).get(0);
        }
        for(int i=1;i<row;i++){
            dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i);
        }
        for(int i=2;i<row;i++){
            for(int j=1;j<triangle.get(i).size()-1;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1])+triangle.get(i).get(j);
            }
        }
        int min=Integer.MAX_VALUE;
        for(int i=0;i<triangle.get(row-1).size();i++){
            min=Math.min(min,dp[row-1][i]);
        }
        return min;
    

    }


Log in to reply
 

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