pascals-triangle.dart (921B)
1 //Given a number of rows return the values contained in each 2 //row of pascals triangle. This solution is the optimal solution using recursion 3 //solution with a time complexity of O(n^2) 4 //There is no reason to use DP in this because there is no request to create multiple 5 //triangles. As such there is no recomputing. 6 //Time: 258ms Beats: 73.26% 7 //Memory: 140.2MB Beats: 88.37% 8 class Solution { 9 List<List<int>> generate(int numRows) { 10 if(numRows == 1){ 11 return [[1]]; 12 } 13 14 15 16 List<List<int>> return_list = generate(numRows-1); 17 return_list.add([]); 18 List<int> last_row = return_list[return_list.length - 2]; 19 List<int> current_row = return_list[return_list.length - 1]; 20 current_row.add(1); 21 for(int i = 1 ; i < last_row.length ; ++i){ 22 current_row.add(last_row[i - 1] + last_row[i]); 23 } 24 current_row.add(1); 25 return return_list; 26 } 27 }