brute force | var minimumTotal = function(triangle) {
let lowest = Infinity
function recursion(row, col, soFar) {
if(row === triangle.length-1) {
lowest = Math.min(soFar, lowest)
return
}
recursion(row+1, col, soFar + triangle[row+1][col])
recursion(row+1, col+1, soFar + triangle[row+1][col+1])
}
recursion(0,0,triangle[0][0])
return lowest
};
minimumTotal([[46],[43,61],[10,-16,3],[-26,41,36,-72],[-28,-76,-22,26,51],[56,-53,38,67,86,-45],[58,53,47,-52,-54,-95,56],[-54,-93,58,68,26,-4,-45,86],[75,28,27,12,33,98,35,87,1],[-13,20,25,-98,-13,11,-44,-77,-59,-97],[-53,-14,83,80,31,89,38,-1,15,-88,53],[-22,86,-41,-94,-25,68,-96,87,55,-18,-49,-25],[-93,-48,39,17,8,61,57,-13,-92,-79,-29,87,51],[-63,3,-72,29,-9,57,-93,-46,-84,88,29,83,69,-7],[15,-49,43,90,-43,94,29,50,-21,-33,-16,43,-26,4,90],[-61,-67,-96,18,-63,32,-91,93,16,-61,86,4,67,46,-27,-63],[-38,0,79,-48,56,51,80,-17,-70,-53,67,49,-3,-52,39,12,-43],[43,-93,-7,-48,91,-13,44,-69,-27,-74,74,95,-25,-88,-43,75,90,8],[8,41,-35,91,48,-12,35,-3,62,59,-86,-49,-83,56,-42,-14,84,-74,72],[6,-44,-78,31,-92,-82,-94,-81,-49,57,85,36,-34,4,77,-66,-71,-34,45,25],[-95,4,15,-45,-3,-52,-11,83,-67,15,32,38,47,54,-54,54,48,-72,72,75,85],[35,11,-72,-61,-11,-62,-33,31,82,68,35,-37,-16,66,37,31,-44,20,40,47,-71,-45],[-6,59,0,-51,7,5,97,-40,-10,32,70,-6,47,-41,31,-86,89,-10,59,1,29,-57,-32],[-34,73,0,62,-9,-53,91,45,17,50,-54,65,-65,50,40,-6,-83,-28,-59,-13,-80,0,94,-90],[-34,-39,68,67,89,-89,-88,-67,61,-12,71,-48,11,62,73,-72,-10,95,70,1,45,10,71,38,58],[-88,-98,54,-12,95,64,31,-44,9,-25,-77,20,-14,-45,-42,73,-74,-14,-16,65,-41,-12,-68,-45,-42,32]])
| ready |
memoization | var minimumTotal = function(triangle) {
let cache = {}
function recursion(row, col) {
if(row===triangle.length) return 0
if(cache[row+','+col]) {
return cache[row+','+col]
} else {
cache[row+','+col] = Math.min(triangle[row][col]+recursion(row+1,col), triangle[row][col]+recursion(row+1,col+1))
}
return cache[row+','+col]
}
return recursion(0,0)
}
minimumTotal([[46],[43,61],[10,-16,3],[-26,41,36,-72],[-28,-76,-22,26,51],[56,-53,38,67,86,-45],[58,53,47,-52,-54,-95,56],[-54,-93,58,68,26,-4,-45,86],[75,28,27,12,33,98,35,87,1],[-13,20,25,-98,-13,11,-44,-77,-59,-97],[-53,-14,83,80,31,89,38,-1,15,-88,53],[-22,86,-41,-94,-25,68,-96,87,55,-18,-49,-25],[-93,-48,39,17,8,61,57,-13,-92,-79,-29,87,51],[-63,3,-72,29,-9,57,-93,-46,-84,88,29,83,69,-7],[15,-49,43,90,-43,94,29,50,-21,-33,-16,43,-26,4,90],[-61,-67,-96,18,-63,32,-91,93,16,-61,86,4,67,46,-27,-63],[-38,0,79,-48,56,51,80,-17,-70,-53,67,49,-3,-52,39,12,-43],[43,-93,-7,-48,91,-13,44,-69,-27,-74,74,95,-25,-88,-43,75,90,8],[8,41,-35,91,48,-12,35,-3,62,59,-86,-49,-83,56,-42,-14,84,-74,72],[6,-44,-78,31,-92,-82,-94,-81,-49,57,85,36,-34,4,77,-66,-71,-34,45,25],[-95,4,15,-45,-3,-52,-11,83,-67,15,32,38,47,54,-54,54,48,-72,72,75,85],[35,11,-72,-61,-11,-62,-33,31,82,68,35,-37,-16,66,37,31,-44,20,40,47,-71,-45],[-6,59,0,-51,7,5,97,-40,-10,32,70,-6,47,-41,31,-86,89,-10,59,1,29,-57,-32],[-34,73,0,62,-9,-53,91,45,17,50,-54,65,-65,50,40,-6,-83,-28,-59,-13,-80,0,94,-90],[-34,-39,68,67,89,-89,-88,-67,61,-12,71,-48,11,62,73,-72,-10,95,70,1,45,10,71,38,58],[-88,-98,54,-12,95,64,31,-44,9,-25,-77,20,-14,-45,-42,73,-74,-14,-16,65,-41,-12,-68,-45,-42,32]])
| ready |
bottom up | var minimumTotal = function(triangle) {
for(var i = triangle.length-2; i>=0; i--) {
let nextRow = triangle[i+1], thisRow = triangle[i]
for(var j = 0; j<thisRow.length; j++) {
thisRow[j]+= Math.min(nextRow[j], nextRow[j+1])
}
}
return triangle[0][0]
};
minimumTotal([[46],[43,61],[10,-16,3],[-26,41,36,-72],[-28,-76,-22,26,51],[56,-53,38,67,86,-45],[58,53,47,-52,-54,-95,56],[-54,-93,58,68,26,-4,-45,86],[75,28,27,12,33,98,35,87,1],[-13,20,25,-98,-13,11,-44,-77,-59,-97],[-53,-14,83,80,31,89,38,-1,15,-88,53],[-22,86,-41,-94,-25,68,-96,87,55,-18,-49,-25],[-93,-48,39,17,8,61,57,-13,-92,-79,-29,87,51],[-63,3,-72,29,-9,57,-93,-46,-84,88,29,83,69,-7],[15,-49,43,90,-43,94,29,50,-21,-33,-16,43,-26,4,90],[-61,-67,-96,18,-63,32,-91,93,16,-61,86,4,67,46,-27,-63],[-38,0,79,-48,56,51,80,-17,-70,-53,67,49,-3,-52,39,12,-43],[43,-93,-7,-48,91,-13,44,-69,-27,-74,74,95,-25,-88,-43,75,90,8],[8,41,-35,91,48,-12,35,-3,62,59,-86,-49,-83,56,-42,-14,84,-74,72],[6,-44,-78,31,-92,-82,-94,-81,-49,57,85,36,-34,4,77,-66,-71,-34,45,25],[-95,4,15,-45,-3,-52,-11,83,-67,15,32,38,47,54,-54,54,48,-72,72,75,85],[35,11,-72,-61,-11,-62,-33,31,82,68,35,-37,-16,66,37,31,-44,20,40,47,-71,-45],[-6,59,0,-51,7,5,97,-40,-10,32,70,-6,47,-41,31,-86,89,-10,59,1,29,-57,-32],[-34,73,0,62,-9,-53,91,45,17,50,-54,65,-65,50,40,-6,-83,-28,-59,-13,-80,0,94,-90],[-34,-39,68,67,89,-89,-88,-67,61,-12,71,-48,11,62,73,-72,-10,95,70,1,45,10,71,38,58],[-88,-98,54,-12,95,64,31,-44,9,-25,-77,20,-14,-45,-42,73,-74,-14,-16,65,-41,-12,-68,-45,-42,32]])
| ready |