LeetCode312. 戳气球

 方法:动态规划,定义二维数组coins,coinsa表示把第a个气球和第b个气球之间(不包括a和b)的气球戳烂,最大能得到的分值

public class Solution {
    public int maxCoins(int[] nums) {
        int[] dpnums = new int[nums.length + 2];
        dpnums[0] = 1;
        dpnums[dpnums.length - 1] = 1;
        for(int i = 0, j = 1; i < nums.length; i++, j++) 
            dpnums[j] = nums[i];
        int[][] coins = new int[dpnums.length][dpnums.length];
        for(int i=2; i<dpnums.length; i++) {
            for(int j=0; j+i<dpnums.length; j++) {
                for(int k=j+1; k<j+i; k++) {
                    coins[j][j+i] = Math.max(coins[j][j+i], coins[j][k] + coins[k][j+i] +
                        dpnums[j] * dpnums[k] * dpnums[j+i]);
                }
            }
        }
        return coins[0][dpnums.length-1];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

学点算法搞安全之HMM(下篇)

前言 我们介绍了HMM的基本原理以及常见的基于参数的异常检测实现,这次我们换个思路,把机器当一个刚入行的白帽子,我们训练他学会XSS的攻击语法,然后再让机器从访...

23080
来自专栏数据结构与算法

BZOJ1563: [NOI2009]诗人小G(决策单调性 前缀和 dp)

\(f_i = min(f_j + (sum_i - sum_j - 1 - L)^P)\)

16530
来自专栏机器学习实践二三事

Tensorflow实现word2vec

大名鼎鼎的word2vec,相关原理就不讲了,已经有很多篇优秀的博客分析这个了. 如果要看背后的数学原理的话,可以看看这个: https://wenku.b...

55570
来自专栏技术沉淀

命令行工具:csvkit命令行操作csv

29160
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

9320
来自专栏Python小屋

Python切分图像小案例(1、3、2、4象限子图互换)

首先解释上一篇文章详解Python科学计算扩展库numpy中的矩阵运算(1)最后的习题,该问题答案是10 ** 8 = 100000000,原因在于Python...

43670
来自专栏贾志刚-OpenCV学堂

OpenCV中图像形态学操作

图像形态学是图像处理的分支学科,在二值图像处理中占有重要地位、OpenCV中实现了图像形态学如下常见操作: -膨胀操作 -腐蚀操作 -开操作 -闭操作 -击中击...

43750
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

10710
来自专栏数据结构与算法

cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互)

\(n\)次操作,每次你给出一个点的坐标,系统会返回该点的颜色(黑 / 白),程序最后输出一条直线把所有黑点和白点分隔开

25340
来自专栏用户2442861的专栏

一致性hash算法 - consistent hashing

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

11210

扫码关注云+社区

领取腾讯云代金券