0
124
VisualizaçõesCómo optimizar la recursividad de JavaScript
Estoy luchando con este problema de codewars en el que tengo que encontrar la suma más alta seleccionando la tarjeta de la izquierda o la derecha. Logré resolver esto usando dos llamadas recursivas para cada lado respectivamente:
function solve(cards, i, j, sum, x) { if (i > j) return sum; var left = solve(cards, i+1, j, sum+(Math.pow(2,x)*cards[i]), x+1 ); var right = solve(cards, i, j-1, sum+(Math.pow(2,x)*cards[j]), x+1 ); return left > right ? left : right; }Creé un diagrama en PowerPoint para mostrar cómo veo mi código. Será como un árbol binario:
Pero la ejecución de mi programa es muy, muy lenta. Por favor, muéstrame cómo puedo hacer esto mejor.
1 Respostas
Responde à pergunta0
Las soluciones más rápidas a este problema no usan la recursividad, usan la programación dinámica donde almacena datos que pueden repetirse varias veces si usa la recursividad. Usando la recursividad, el tiempo de ejecución aumentará exponencialmente con cada elemento agregado a la lista de tarjetas. Aquí hay una solución más rápida usando Programación Dinámica.
function calc(cards){ let n = cards.length; let dp = Array.from(Array(n), _ => Array(n).fill(0)); for (let i = 0; i < n; i++) dp[0][i] = 2 * cards[i]; for (let i = 1; i < n; i++) for (let j = 0; j < n - i; j++) dp[i][j] = Math.max(dp[i - 1][j] * 2 + dp[0][i + j], dp[i - 1][j + 1] * 2 + dp[0][j]); return dp[n - 1][0] } console.log(calc([1,2,5])) console.log(calc([1])) console.log(calc([1,1])) console.log(calc([1,2,1])) console.log(calc([4, 10, 2, 3, 1, 3, 1, 6, 9]))