本文共 1381 字，大约阅读时间需要 4 分钟。
有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。
**区间型动态规划问题+记忆化搜索
从大到小 类似分治的思想 dp数组代表吹爆序号i到j的气球得到的最多分数 为了方便边界两个气球的运算 在左右边界添加一个元素1 用一个二维数组记录已经搜索过的区间情况 对数组每个元素作为最后吹爆的气球进行遍历 搜索每个元素左右两边区间 dfs **public class Solution { /** * @param nums: A list of integer * @return: An integer, maximum coins */ public int maxCoins(int[] nums) { int n = nums.length; if(nums == null || n == 0) return 0; int[] arr = new int[n+2]; int[][] dp = new int[n+2][n+2]; boolean[][] flag = new boolean[n+2][n+2]; for(int i = 1; i < n + 1; i++){ arr[i] = nums[i-1]; } arr[0] = 1; arr[n + 1] = 1; return search(1, n, arr, dp, flag); } private int search(int left, int right, int[] arr, int[][] dp, boolean[][] flag){ if(flag[left][right]) return dp[left][right]; for(int k = left; k <= right; k++){ int midValue = arr[left-1] * arr[k] * arr[right+1]; int leftValue = search(left, k-1, arr, dp, flag); int rightValue = search(k+1, right, arr, dp, flag); dp[left][right] = Math.max(dp[left][right], midValue + leftValue + rightValue); } flag[left][right] = true; return dp[left][right]; }} 转载地址：http://exvv.baihongyu.com/