triangle.dart (1136B)
1 //Given a matrix of i + 1 size where i is the index of the list (0 index) 2 //return the minimum path from the top to the bottom where you can only either 3 //go to i or i+1 on the row below the current row. 4 //The time complexity of this code is O(n^2) 5 //Time: TLE 6 //Memory: TLE 7 class Solution { 8 List<List<int>> triangle = []; 9 int minimumTotal(List<List<int>> tri) { 10 triangle = tri; 11 return min( 0, 0, {}); 12 } 13 14 int min(int current_index , int row, Map<String,int> memo){ 15 if(memo.containsKey(current_index.toString() + " " + row.toString())){ 16 int current_val = (memo[current_index.toString() + " " + row.toString()] ?? 0); 17 return current_val; 18 } 19 if(row == triangle.length){ 20 return 0; 21 } 22 int curr = min( current_index , row + 1 , memo); 23 int right = min( current_index + 1 , row + 1, memo); 24 if(curr < right){ 25 return curr + triangle[row][current_index]; 26 } 27 int lowest_for_index = right + triangle[row][current_index]; 28 memo[current_index.toString() + " " + row.toString()] = lowest_for_index; 29 return lowest_for_index; 30 } 31 }