0
122
VistasHow to optimize recursion JavaScript
I am struggling with this codewars problem where I have to find the highest sum by selecting the card on the left or right. I managed to solve this using two recursive calls for each side respectively:
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;
}
I created a diagram in PowerPoint to show how I see my code. It will be like a binary tree:
But the execution of my program is very very slow. Please show me how I can do this better.
·
Juan Pablo Isaza
1 Respuestas
Responde la pregunta0
The faster solutions to this problem don't use recursion, they use Dynamic Programming where you store data that might be repeated multiple times if you use recursion. Using recursion, the execution time will increase exponentially with every added element to the card list. Here's a faster solution using Dynamic Programming.
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]))
·
Juan Pablo Isaza
Denunciar
Responde la pregunta