第一次遇到区间dp的题

分析

题目

• 这道题可以用dp思想+分治思想求解
• dp[i][j] 表示开区间 (i,j) 内你能拿到的最多硬币
• 任意选择(i, j)之间气球k，且k是最后一个被戳爆的
• 那么可以得到状态转移方程：dp[i][j] = Max(dp[i][k] + temp[i] * temp[k] * temp[j] + dp[k][j])(k在区间内枚举)
• 从方程中就可以看出分治思想：从k处将问题划分为了2个子问题，dp的思路就是先求解最初的子问题，然后由转移方程一步一步得出结果
• 至于为什么是开区间？可以这样想，temp数组的两端是假想的气球，不能被戳

Java实现

class Solution {public int maxCoins(int[] nums) {int n = nums.length;int[] temp = new int[n+2];//创建一个辅助数组，并在首尾各添加1，方便处理边界情况temp[0] = 1;temp[n+1] = 1;for(int i=0; itemp[i+1] = nums[i];}int[][] dp = new int[n+2][n+2];for(int len=3; len<=n+2; len++){//len表示开区间长度for(int i=0; i<=n+2-len; i++){//i表示开区间左端点int res = 0; for(int k = i+1; k//k为开区间内的索引int left = dp[i][k];int right = dp[k][i+len-1];res = Math.max(res, left + temp[i]*temp[k]*temp[i+len-1] + right);}dp[i][i+len-1] = res;}}return dp[0][n+1];}
}

• 很容易得出T=O(n3),S=O(n2)T=O(n^3), S=O(n^2)T=O(n3),S=O(n2)