LeetCode_动态规划_困难_312.戳气球

x33g5p2x  于2022-03-07 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(164)

1.题目

有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界,那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量

示例 1:
输入:nums = [3,1,5,8]
输出:167
解释:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [ ]
coins = 3 * 1 * 5 + 3 * 5 * 8 + 1 * 3 * 8 + 1 * 8 * 1 = 167

示例 2:
输入:nums = [1,5]
输出:10

提示:
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/burst-balloons

2.思路

(1)动态规划
具体思路参考经典动态规划:戳气球问题

3.代码实现(Java)

//思路1————动态规划
public int maxCoins(int[] nums) {
    int length = nums.length;
    int[] scores = new int[length + 2];
    //在原始数组两侧添加“虚拟气球”,分数均为1
    scores[0] = scores[length + 1] = 1;
    //初始化scores
    for (int i = 1; i <= length; i++) {
        scores[i] = nums[i - 1];
    }
    //dp[i][j]:表示戳破气球i和气球j之间(不包括i和j)的所有气球,可以获得的最高分数
    int[][] dp = new int[length + 2][length + 2];
    //i:length->0
    for (int i = length; i >= 0; i--) {
        //j:i+1->length + 1
        for (int j = i + 1; j <= length + 1; j++) {
            //最后戳破的气球
            for (int k = i + 1; k < j; k++) {
                /*
                    择优做选择
                    在区间(i, j)中,如果最后戳破气球为k,那么开区间(i, k)和(k, j)的气球都已被戳破
                    最后剩下的气球为k,相邻的就是气球i和气球j,所以这时的得分为 scores[i]*scores[k]*scores[j]                    
                */
                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + scores[i] * scores[k] * scores[j]);
            }
        }
    }
    return dp[0][length + 1];
}

相关文章

微信公众号

最新文章

更多