class Solution { public int maxCoins(int[] nums) { int n = nums.length + 2; int[] new_nums = new int[n]; for(int i = 0; i < nums.length; i++){ new_nums[i+1] = nums[i]; } new_nums[0] = new_nums[n - 1] = 1; // cache the results of dp int[][] memo = new int[n][n]; // find the maximum number of coins obtained from adding all balloons from (0, len(nums) - 1) int ans = 0; // manually burst the last balloon because it has special rules for(int i = 1; i < n; ++i){ ans = Math.max(ans, new_nums[i] + dp(memo, new_nums, i, n - 1) + dp(memo, new_nums, 0, i)); } return ans; } public int dp(int[][] memo, int[] nums, int left, int right) { // no more balloons can be added if (left + 1 == right) return 0; // we've already seen this, return from cache if (memo[left][right] > 0) return memo[left][right]; // add each balloon on the interval and return the maximum score int ans = 0; for (int i = left + 1; i < right; ++i) ans = Math.max(ans, nums[left] * nums[right] + dp(memo, nums, left, i) + dp(memo, nums, i, right)); // add to the cache memo[left][right] = ans; return ans; }}输入:[1, 2, 3, 4][5, 7, 8]输出:2056
添加回答
举报
0/150
提交
取消