Why my code gets wrong answer?

• 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;
}``````

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

• 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];
}
}``````

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