JavaScript Top Down And Bottom Up DP Solution
For both solutions: Time: O(N^3) and Space: O(N^2)\n## Solution 1: Top Down\njavascript\nvar maxCoins = function(nums) {\n    nums.push(1);\n    nums.unshift(1)
For both solutions: Time: `O(N^3)` and Space: `O(N^2)`\n## Solution 1: Top Down\n```javascript\nvar maxCoins = function(nums) {\n    nums.push(1);\n    nums.unshift(1);\n    \n    const memo = [...Array(nums.length)].map(() => Array(nums.length).fill(0));\n    \n    function split(start, end) {\n        if(start > end) return 0\n        if(memo[start][end]) return memo[start][end];\n        \n        let max = 0;\n        \n        for(let i = start; i <= end; i++) {\n            const left = split(start, i-1);\n            const right = split(i+1, end);\n            const currBurst = nums[start-1] * nums[i] * nums[end+1]\n            const coin = left + currBurst + right;\n            max = Math.max(max, coin);\n        }\n        memo[start][end] = max;\n        return max;\n    }\n    return split(1, nums.length-2)\n};\n```\n\n## Solution 2: Bottom Up\n```javascript\nvar maxCoins = function(nums) {\n    nums.push(1);\n    nums.unshift(1);\n    const dp = [...Array(nums.length)].map(() => Array(nums.length).fill(0));\n    \n    for(let windowSize = 1; windowSize < nums.length-1; windowSize++) {\n        for(let start = 1, end = windowSize; end < nums.length-1; end++, start++) {\n            for(let i = start; i <= end; i++) {\n                const coins = dp[start][i-1] + (nums[start-1] * nums[i] * nums[end+1]) + dp[i+1][end];\n                dp[start][end] = Math.max(dp[start][end], coins);\n            }\n        }\n    }\n    return dp[1][nums.length-2]\n};\n```\n\n
['Dynamic Programming', 'JavaScript']