Leetcode 312. Burst Balloons (python+cpp)

题目

解法1：backtracking brutal force

这道题目应该算是个分治法和动态规划的结合体，个人感觉很难。当然想出backtracking这种方法还是比较直观的，但是在这里backtracking的复杂度会是n的阶乘，肯定是过不了的，不过也在这边写一下这种方法，方便理解题目
python代码如下：

class Solution:def maxCoins(self, nums: List[int]) -> int:def back_tracking(coins,nums):nonlocal ansif not nums:ans = max(coins,ans)returnfor i in range(len(nums)):tmp = nums[i]delta = nums[i]*(1 if i<1 else nums[i-1])*(1 if i+2>len(nums) else nums[i+1])back_tracking(coins+delta,nums[:i]+nums[i+1:])ans = 0back_tracking(0,nums)return ans

解法2：逆向考虑

这种解法其实说实话也挺难理解的，所以暂时先把解法放在这，包括改进的写法，等后面想清楚了再来补充吧，不过感兴趣的同学可以参考这个链接的讲解，思路相对来说还比较清晰，还有带着大家直接写码，比较良心了https://www.youtube.com/watch?v=_4qGDebH_ws
python代码如下：

class Solution:def maxCoins(self, nums: List[int]) -> int:def dfs(i,j):if i>j:return 0if (i,j) in memo:return memo[(i,j)]for k in range(i,j+1):left = dfs(i,k-1)right = dfs(k+1,j)delta = nums[k]*nums[i-1]*nums[j+1]if (i,j) in memo:memo[(i,j)] = max(memo[(i,j)],left+right+delta)else:memo[(i,j)] = left+right+deltareturn memo[(i,j)]memo = {
    }nums = [1]+nums+[1]return dfs(1,len(nums)-2)

C++代码如下：

class Solution {
    
public:int maxCoins(vector<int>& nums) {
    int n = nums.size();nums.insert(nums.begin(),1);nums.push_back(1);vector<vector<int>> dp(n+2,vector<int>(n+2,0));return dfs(nums,dp,1,n);}int dfs(vector<int>& nums,vector<vector<int>>& dp,int i,int j){
    if (i>j) return 0;if (dp[i][j]>0) return dp[i][j];for (int k=i;k<=j;k++){
    int left = dfs(nums,dp,i,k-1);int right = dfs(nums,dp,k+1,j);int delta = nums[k]*nums[i-1]*nums[j+1];dp[i][j] = max(dp[i][j],left+right+delta);}return dp[i][j];}
};