通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

LeetCode 312. Burst Balloons(戳气球)

5465人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  | 

作者:因情语写

链接:https://www.proprogrammar.com/article/91

声明:请尊重原作者的劳动,如需转载请注明出处


    参考:LeetCode 312. Burst Balloons(戳气球)

    java代码如下

class Solution {
    //参考:https://blog.csdn.net/jmspan/article/details/51208865
    public int maxCoins(int[] nums) {
        int[] balls = new int[nums.length+2];
        balls[0] = 1;
        balls[balls.length - 1] = 1;
        int[][] coins = new int[balls.length][balls.length];
        for(int i = 0; i < nums.length; i++)
        {
            balls[i+1] = nums[i];
        }
        
        for(int j = 2; j < balls.length; j++)
        {
            for(int i = j - 2; i >= 0; i--)
            {
                for(int k = j -1; k > i; k--)
                {
                    /* 这个里面的coins[i][k]  + balls[i]*balls[k]*balls[j] + coins[k][j]
                        是最大的可以这样理解:以k分割(为什么会有k,因为无论怎么戳,最后剩三个
                        的时候,一定是i,j和另一个,另一个就是k,那么要总的结果最大,那么要k
                        两边的值都取最
                        大,两边值最大是什么:即coins[i][k],coins[k][j],先戳两边的把两个最
                        大找出来,最后左右两边剩什么呢,正是最左边的balls[i]和最右边的balls[j],
                        最后处理k处的即balls[i]*balls[k]*balls[j]
                    */
                    coins[i][j] = Math.max(coins[i][j], coins[i][k]
                                          + balls[i]*balls[k]*balls[j] + coins[k][j]);
                }
            }
        }
        
        return coins[0][balls.length - 1];
    }
}

    代码中分析了重点代码,采用了动态规划,从最小的情况出发,慢慢扩大,每次都取最大(最优)的结果,最终的结果也是最优的

    三层循环:j:最右值,i:最左值,k:中间值,三层循环从小到大获取不同长度,不同位置的数组的一段的最值coins[i][j],coins[i][j]不包括两端,初始时coins是int数组默认都是0,符合实际情况,最后返回一个最长的也即最大的结果,难点就是分析到数组的某一段剩3个元素i,j,k时的情形,可以根据这个情形反推之前要如何处理,即k前后都取最大,即这时的最大值为coins[i][k] + balls[i]*balls[k]*balls[j] + coins[k][j],个人见解,希望对你有帮助。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告