JavaScript
let cache = new Map();
function maxPathWeight( pyramid, floor, position) {
let currentNode = pyramid[floor][position];
// cuando llegamos a la base de la piramide, retornamos
// para acumularlo
if (floor === pyramid.length - 1){
return currentNode;
}
// creamos una key, ejemplo: 2,1
var key = floor + ',' + position;
// si el nodo ya ha sido visitado, retornamos su valor
if (cache.get(key) !== undefined) {
return cache.get(key);
}
// calculamos el acumulado del lado izquierdo hacia abajo
let leftPath = currentNode + maxPathWeight(pyramid, floor + 1, position);
// calculamos el acumulado del lado derecho hacia abajo
let rightPath = currentNode + maxPathWeight(pyramid, floor + 1, position + 1);
// lo guardamos en caché
cache.set(key, Math.max(leftPath, rightPath));
// retornamos el máximo de los acumulados
return Math.max(leftPath, rightPath);
}
function longestPath( ) {
let pyramid =
[
[59],
[73, 41],
[52, 40, 9],
[26, 53, 6, 34],
[10, 51, 87, 86, 81],
[61, 95, 66, 57, 25, 68],
[90, 81, 80, 38, 92, 67, 73],
[30, 28, 51, 76, 81, 18, 75, 44],
[84, 14, 95, 87, 62, 81, 17, 78, 58],
[21, 46, 71, 58, 2, 79, 62, 39, 31, 9],
[56, 34, 35, 53, 78, 31, 81, 18, 90, 93, 15],
[78, 53, 4, 21, 84, 93, 32, 13, 97, 11, 37, 51],
[45, 3, 81, 79, 5, 18, 78, 86, 13, 30, 63, 99, 95],
[39, 87, 96, 28, 3, 38, 42, 17, 82, 87, 58, 7, 22, 57],
[6, 17, 51, 17, 7, 93, 9, 7, 75, 97, 95, 78, 87, 8, 53],
[67, 66, 59, 60, 88, 99, 94, 65, 55, 77, 55, 34, 27, 53, 78, 28],
[76, 40, 41, 4, 87, 16, 9, 42, 75, 69, 23, 97, 30, 60, 10, 79, 87],
[12, 10, 44, 26, 21, 36, 32, 84, 98, 60, 13, 12, 36, 16, 63, 31, 91, 35],
[70, 39, 6, 5, 55, 27, 38, 48, 28, 22, 34, 35, 62, 62, 15, 14,...