DP solution beats 98%


  • 0
    C

    Used memoization to prevent resolving sub-problems.

    public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
    int memo[][]=new int[triangle.size()][triangle.get(triangle.size()-1).size()];

        return minimumTotal(triangle,0,0,memo);
    }
    
    int minimumTotal(List<List<Integer>> triangle,int headPos,int colPos,int [][]memo){
        if(headPos>=triangle.size()||colPos>=triangle.get(headPos).size())
            return 0;
        if(memo[headPos][colPos]!=0)
            return memo[headPos][colPos];
            
        int min=Integer.MAX_VALUE;
        
        int left=minimumTotal(triangle,headPos+1,colPos,memo);
        int right=minimumTotal(triangle,headPos+1,colPos+1,memo);
        
        memo[headPos][colPos]=left<right?left+triangle.get(headPos).get(colPos):right+triangle.get(headPos).get(colPos);
        return memo[headPos][colPos];
    }
    

    }


Log in to reply
 

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