💥Runtime beats 95.06% [EXPLAINED]
Intuition\nThe intuition behind solving the "Burst Balloons" problem is to use dynamic programming to systematically determine the best order to burst balloons 
# Intuition\nThe intuition behind solving the "Burst Balloons" problem is to use dynamic programming to systematically determine the best order to burst balloons for maximum coins.\n\n# Approach\nThis dynamic programming approach efficiently computes the maximum coins by systematically solving smaller subproblems and using those solutions to build up to the final answer.\n\n# Complexity\n- Time complexity:\nO(n3), where n is the length of the nums array. This comes from the three nested loops used to fill the DP table.\n\n- Space complexity:\nO(n2) for the DP table.\n\n# Code\n```typescript []\nfunction maxCoins(nums: number[]): number {\n    const n = nums.length;\n    const extendedNums = [1, ...nums, 1]; // Add 1 before and after nums array\n\n    // Initialize the DP table\n    const dp: number[][] = Array.from({ length: n + 2 }, () => Array(n + 2).fill(0));\n\n    // Fill the DP table\n    for (let length = 1; length <= n; length++) {\n        for (let left = 1; left <= n - length + 1; left++) {\n            const right = left + length - 1;\n            for (let i = left; i <= right; i++) {\n                dp[left][right] = Math.max(\n                    dp[left][right],\n                    dp[left][i - 1] + extendedNums[left - 1] * extendedNums[i] * extendedNums[right + 1] + dp[i + 1][right]\n                );\n            }\n        }\n    }\n\n    return dp[1][n];\n}\n\n```
['TypeScript']