space O(n) DP solution


  • 0
    S

    bottom up method, dp[j]=Math.min(dp[j],dp[j+1])+tp.get(j) , update dp[j] wont overwrite any information concerns with updating dp[j+1], i.e.dp[j+1] and dp[j+2]

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

    }

Log in to reply
 

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