Q:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Sulotion:
public class Solution { public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) { // Start typing your Java solution below // DO NOT write main() function if(triangle == null){ return 0; } ArrayList<int[]> table = new ArrayList<int[]>(); for(ArrayList<Integer> tmp : triangle){ table.add(new int[tmp.size()]); } return minTotal(table,triangle,0,0); } public int minTotal(ArrayList<int[]> table, ArrayList<ArrayList<Integer>> triangle, int row,int column){ if(row == triangle.size()-1){ table.get(row)[column]=triangle.get(row).get(column); }else if(table.get(row)[column]==0){ table.get(row)[column]=(Math.min(minTotal(table,triangle,row+1,column+1),minTotal(table,triangle,row+1,column)))+triangle.get(row).get(column); } return table.get(row)[column]; }}
Hint: there is an important cache implementation to reduce the time complexity. if(table.get(row)[column]==0)