C++ dp detailed explanation
the visualization help me to understand hope it can help you too.\n\n   1\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb71 \n\nadd t
the visualization help me to understand hope it can help you too.\n\n   1\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb71 \n\nadd two 1 at beginning and end of nums, each \xb7 represent each number in nums.\n\n   len is the subinterval length, it grows from 1 to full length of orignal nums string.\n\n   the following illustrations demonstrate how the subinterval shift from left to right. (len = 7 in the illustration)\n\n   for each len, when shifted to rightmost, increase len and do the shift again. this way we can evaluate all possible subintervals.\n\n   for each subinterval, in the innermost for loop, find which balloon to burst LAST that will give us the most coins for that subinterval. <- IMPORTANT TO UNDERSTAND THIS\n\n   `dp[left][right]` is the maximum coins we can get from left to right. note when  left > right, it is 0\n    \n       1\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb71    (len = 7)\n        |     |\n      left  right\n      \n       1\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb71\n               |     |\n             left  right\n              \n       1\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb7\xb71\n                    |     |\n                  left  right\n\n   \n   for the example [3, 1, 5, 8], the dp matrix is updated like this\n\n    0    0    0    0    0    0\n    0    3    0    0    0    0\n    0    0    15   0    0    0\n    0    0    0    40   0    0\n    0    0    0    0    40   0\n    0    0    0    0    0    0\n\nthen\n\n    0    0    0    0    0    0\n    0    3    30   0    0    0\n    0    0    15   135  0    0\n    0    0    0    40   48   0\n    0    0    0    0    40   0\n    0    0    0    0    0    0\n\nat last\n   \n    0    0    0    0    0    0\n    0    3    30   159  167  0\n    0    0    15   135  159  0\n    0    0    0    40   48   0\n    0    0    0    0    40   0\n    0    0    0    0    0    0\nthe code is like most others.\n\n    class 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(nums.size(), vector<int>(nums.size(), 0));\n            for (int len = 1; len <= n; ++len)\n                for (int left = 1; left <= n - len + 1; ++left) {\n                    int right = left + len - 1;\n                    for (int k = left; k <= right; ++k)\n                        dp[left][right] = max(dp[left][right], nums[left-1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]);\n                }\n            return dp[1][n];\n        }\n    };
['Dynamic Programming']