牛客74234309号

题解

/ 注册

全部文章 / 题解（共11篇）

题解 | #合唱队形#

两个维度的动态规划 import java.util.*; public class Main{ public static void main(String []args){ ...

Java 动态规划

2022-03-11

3 372

题解 | #合唱队形#

动态规划分别求出每个位置元素的左边最长递增序列和右边最长递减序列，求和之后取最大，就是符合的合唱队形，用总人数减去合理的人数就是所求结果。 import java.util.*; public class Main{ &n...

Java 动态规划

2022-03-11

0 383

题解 | #龙与地下城游戏问题#

从终点开始动态规划 import java.util.*; public class Main{ public static void main(String []args){ ...

Java 动态规划

2022-03-11

3 786

题解 | #分割等和子集#

01背包问题，value为num[i],weight也是num[i] import java.util.*; public class Main{ public static void&nb...

Java 动态规划

2022-03-09

0 406

题解 | #兑换零钱#

完全背包，注意dp的初始化 import java.util.*; public class Main{ static int maxValue=0; ...

Java 动态规划

2022-03-09

0 574

题解 | #最大子矩阵#

本题目类似于柱状图中最大矩形，不过那一题使用单调栈做的（只有0和1），本题的话也可以用类似的思路，遍历矩形的行的起点和终点组合，然后相当于就是求解最大连续子数组和，最后取全局最大。 import java.util.*; public class Main{ &nb...

Java 动态规划

2022-03-08

2 725

题解 | #环形数组连续最大和#

同时维护最大最小，全是负数的时候额外考虑一下。 import java.util.*; public class Main{ public static void main(String&...

Java 动态规划

2022-03-07

0 577

题解 | #乘积为整数的最长连续子数组#

动态规划，同时维护最长连续正数和最长连续负数 import java.util.*; public class Main{ public static void main(String&n...

Java 动态规划

2022-03-07

4 868

题解 | #最长上升子序列(三)#

动态规划+二分查找，状态转移公式跟普通的有所不同，用tail数组维护当前最长的公共子序列，如果arr[i]>当前tail[len-1],则tail[len++]=arr[i],dp[i]=len; 如果不成立，则通过二分查找到最小的大于等于arr[i]的位置，插入arr[i]（这样才...

Java 动态规划二分查找

2022-02-13

0 403

题解 | #编辑距离(二)#

动态规划解决编辑距离问题，注意dp数组的初始化，dp[i][j]的意义是str1中的i-1子字符串到str2中j-1结尾的字符串的最短编辑距离 import java.util.*; public class Solution { /** &n...

Java 动态规划字符串

2022-01-21

0 299