Why my code gets wrong answer?


  • 0
    X

    Hey,

    I wrote this DP solution for this problem and I was told it got wrong answer. But I cannot find where I made a mistake. Can anyone help to see what's wrong with this code? Any help will be really appreciated!

    public class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        int sum = 0;
        int min = Integer.MAX_VALUE;
        int lenth = triangle.size();
        
        //Start from the bottom row and get the minimum path-value from triangle[0][0] to this element.
        //get the final min value, by comparing 
        for(int i = 0; i < triangle.get(lenth-1).size(); i++) {
            sum = minimum(triangle,lenth-1,i,map);
            if(sum < min) {
                min = sum;
            }
        }
        return min;
    }
    
    /**
     * Get the min path-value from triangle[0][0] to triangle[x][y].
     * When finding a min path-value,store it in the HashMap.
     * */
    public int minimum(List<List<Integer>> triangle, int x, int y, HashMap<String,Integer> map) {
        if(0 == x && 0 == y) {
            return triangle.get(0).get(0);
        }
        
        String key = Integer.toString(x)+Integer.toString(y);
        if(map.containsKey(key)) {
            return map.get(key);
        }
        
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        int sum = 0;
        
        if(y-1 >= 0) {
            left = minimum(triangle,x-1,y-1,map);
        }
        if(y < triangle.get(x).size()-1) {
            right = minimum(triangle,x-1,y,map);
        }
        sum = triangle.get(x).get(y) + (left <= right? left : right);
        map.put(key,new Integer(sum));
        return sum;
    }

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    M

    My code uses dynamic programming with O(n) extra space. Hope it helps you. If you have any doubts, please comment.

    public class Solution 
    {
        public int minimumTotal(List<List<Integer>> triangle)
        {
            if((triangle==null)||(triangle.size()==0))
            {
                return -1;
            }
            int n=triangle.size();
    
            int[] A= new int[n];
            
            for(int i=0;i<n;i++)
            {
                A[i]=triangle.get(n-1).get(i);
            }
            
            for(int i=n-2;i>=0;i--)
            {
                List<Integer> list= triangle.get(i);
                for(int j=0;j<list.size();j++)
                {
                    A[j]=list.get(j)+Math.min(A[j],A[j+1]);
                }
            }
            
            return A[0];
        }
    }

Log in to reply
 

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