Some Time We Need To Skip Recursion And Jump With Iterative Intuition
On first time when I saw this problem, I think that we came with the intuition :\n1. We will burst all the ballon.\n2. And for each ballon we can have two optio
On first time when I saw this problem, I think that we came with the intuition :\n1. We will burst all the ballon.\n2. And for each ballon we can have two options:\n      1. Either I can burst it or,\n      2. I can skip it.\n\n\nBut this intuition got failed after looking at some hints. I tried to figure out that :\n\nLet\u2019s suppose we are going to burst the ballon in the range [left\u2026.right] so,\n\n1. This range can vary from 0...N.\n2. For each [left, right], we will burst every ballon and get the possible maximum coins for this [left, right]\n3. In such a way, we have explored all the ranges of bursting the ballon and we required the range from [left=1\u2026 right=n] i.e. full length.\n\nSo,\n\n1. My, Dp[left][right] = {Will tell you that what will be the maximum coins if you burst all the ballon from left to right.}\n2. Let\u2019s suppose we bursting i-th ballon :\n3. So we\u2019ll get the coin :\n4.  `(dp[left][i-1] + dp[i+1][right]) + (nums[burn] * nums[left - 1] * nums[right + 1])`\n5.  **dp[left][i-1] + dp[i+1][right] :** total coin from [left\u2026 right] after burning i-th ballon will be  coins of [left...i] and coins[i+1...right] because nums[i] is going to be burned plus coins what we will get extra after burning i-th ballon(i.e. nums[i] * nums[left - 1] * nums[right + 1])\n\n\n```\n\nclass Solution {\n   public:\n    int maxCoins(vector<int>& nums) {\n        int n = nums.size();\n        nums.insert(nums.begin(), 1);\n        nums.push_back(1);\n        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));\n\n        // Let\'s extract from small length to n\n        for (int len = 1; len <= n; len++) {\n            for (int left = 1; left <= n - len + 1; left++) {\n                // Get the right range\n                int right = left + len - 1;\n                int bestCoin = 0;\n\n                // Find the maximum possible coins if we burned all the ballon in the rand left to right\n                for (int burn = left; burn <= right; burn++) {\n                    // total coin from [left...burn-1] and [burn+1...right] because [burn] is going to be burned\n                    int coins = dp[left][burn - 1] + dp[burn + 1][right];\n                    coins += (nums[burn] * nums[left - 1] * nums[right + 1]);\n                    bestCoin = max(bestCoin, coins);\n                }\n\n                // Store the answer\n                dp[left][right] = bestCoin;\n            }\n        }\n\n        // return the max coins which getting after burning from 1-n\n        return dp[1][n];\n    }\n};\n\n\n```\n\n\n
[]