After 3 days of thinking got the solution with full intiution DP memoization
so I\'ve been solving this problem from past 3 days and finally get to know the correct intution so this is a partition problem as you can see you have to calcu
**so I\'ve been solving this problem from past 3 days and finally get to know the correct intution so this is a partition problem as you can see you have to calculate the cost for each and every balloon burst right? so the intution is quite different from other questions you have to assume that the balloon you gonna burst is the last one therefore it\'s left part and right part already got burst since there is no one to combine with that last balloon you would get the cost to burst that balloon is  1 x balloon x 1 and the total cost is { left part cost + 1 x balloon x 1 + right part cost } and you have to do this thing for all the partitions I guess it\'s enough intution let back to the code right? with comments ofc**\n```\nclass Solution {\npublic:\n    vector<int>v;    // this is the new vector with new modification as [ 1 , oldArray , 1 ] because the question already said this if your i-1 or i +1 goes out of bound you have 1 to multiply with \n    int dp[505][505];\n    //matrix-chain-multiplication\n    int go( int si, int ei){\n        if(dp[si][ei]!=-1)return dp[si][ei];\n       if(si>ei)return 0;\n       if(si==ei)return v[si-1]*v[si]*v[si+1];    //if you only have 1 element in your array\n        int ans = INT_MIN;\n       for(int k = si ; k<=ei ; k++){ \n\t\t   //let suppose the last balloon is at kth position to \n\t\t   //burst how will you burst this balloon? ofc with v[si-1] * v[ k ] * v[ ei +1 ] \n\t\t   //now please dry run this step in your notebook \n\t\t   //as v[ si -1 ] = v[ ei + 1 ] = 1 so basically it\'s 1 * v[k] * 1\n\t\t   int cur = v[si-1]*v[k]*v[ei+1]; \n           int pre = go(si,k-1);     // the cost from it\'s left part\n           int post = go(k+1,ei); // the cost from it\'s right part \n           int total = cur+pre+post;  //total cost is the sum of all the combinations \n           ans = max(ans,total);  // store the maximum one \n       }\n        return dp[si][ei] = ans;\n    }\n    int maxCoins(vector<int>& nums) {\n        memset(dp,-1,sizeof(dp));\n        v.clear();\n        v.push_back(1);                 // creating a new vector v so that it will contain 1 at both the ends of array \n        for(auto val : nums)\n            v.push_back(val);\n        v.push_back(1);\n        return go(1,nums.size());\n    }\n};\n```\n\n**hope y\'all like this please don\'t downvote it even if you didn\'t understand because  it took 15 minutes to write this Updated the comment Section**
[]