C++ DP Solution O(N^3)
dp[i][j] represents the maximum coins we get after we burst all the balloons from i to j.\nLet Kth is the last balloon to be burst in thr interval [i,j] then,\n
dp[i][j] represents the maximum coins we get after we burst all the balloons from i to j.\nLet Kth is the last balloon to be burst in thr interval [i,j] then,\ndp[i][j] = maximum value of bursting all the balloon on the left side of \'K\' + maximum value of bursting all the balloon on the right side of \'K\' + bursting balloon \'K\' when left side and right side are gone.\ndp[i][j] = dp[i][K-1] + (A[i-1] * A[K] * A[j+1]) + dp[K+1][j]\n```\nint maxCoins(vector<int>& A) {\n\tint n = A.size();\n\tA.insert(A.begin(), 1);\n\tA.push_back(1);\n\tvector<vector<int>> dp(n+2, vector<int>(n+2, 0));\n\tfor(int len = 1; len <= n; len++) {\n\t\tfor(int start = 1; start <= n-len+1; start++) {\n\t\t\tint end = start + len -1;\n\t\t\tfor(int k = start; k <= end; k++) {\n\t\t\t\tdp[start][end] = max(dp[start][end], dp[start][k-1] + (A[start-1] * A[k] * A[end+1]) + dp[k+1][end]);\n\t\t\t}\n\t\t}\n\t}\n\treturn dp[1][n];\n}\n```\nRecursive Solution\n```\nint maxCoins(vector<int>& A) {\n\tint n = A.size();\n\tA.insert(A.begin(), 1);\n\tA.push_back(1);\n\tvector<vector<int>> dp(n+2, vector<int>(n+2, -1));\n\treturn helper(A, dp, 1, n);\n}\n\nint helper(vector<int>& A, vector<vector<int>>& dp, int start, int end) {\n\tif (start > end) return 0;\n\tif (dp[start][end] != -1) return dp[start][end];\n\tfor (int k = start; k <= end; k++)\n\t\tdp[start][end] = max(dp[start][end], helper(A, dp, start, k-1) + helper(A, dp, k+1, end) + A[start-1] * A[k] * A[end+1]);\n\treturn dp[start][end];\n}\n```
['Dynamic Programming', 'Recursion', 'C', 'C++']