JoyAI LeetCode 312.戳气球 public int maxCoins(int[] nums)

这道题是 LeetCode 上的“戳气球”问题，属于动态规划中的经典题目。我们需要找到戳破所有气球能获得的最大硬币数。下面是解题思路和代码实现：

解题思路

1. 问题转换：为了避免边界问题，我们在原数组首尾各添加一个值为1的元素。
2. 定义状态：dp[i][j]表示戳破区间(i,j)内所有气球（不包括i和j）能获得的最大硬币数。
3. 状态转移：对于区间(i,j)，枚举最后一个被戳破的气球k，则dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])。

代码实现

publicintmaxCoins(int[]nums){intn=nums.length;int[]newNums=newint[n+2];newNums[0]=1;newNums[n+1]=1;for(inti=1;i<=n;i++){newNums[i]=nums[i-1];}int[][]dp=newint[n+2][n+2];for(intlen=3;len<=n+2;len++){// 区间长度for(inti=0;i+len-1<=n+1;i++){// 左端点intj=i+len-1;// 右端点for(intk=i+1;k<j;k++){// 枚举最后一个戳破的气球dp[i][j]=Math.max(dp[i][j],dp[i][k]+dp[k][j]+newNums[i]*newNums[k]*newNums[j]);}}}returndp[0][n+1];}

复杂度分析

• 时间复杂度：O(n³)，三重循环。
• 空间复杂度：O(n²)，二维DP数组。

这个解法通过动态规划自底向上地计算每个区间的最优解，最终得到整个区间的最优解。希望这个解释对你有帮助！如果有任何疑问，欢迎继续讨论。