两个维度的动态规划 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);         int&nb...

动态规划 分别求出每个位置元素的左边最长递增序列和右边最长递减序列，求和之后取最大，就是符合的合唱队形，用总人数减去合理的人数就是所求结果。 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(Sy...

从终点开始动态规划 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);         int&nb...

01背包问题，value为num[i],weight也是num[i] import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);     &...

完全背包，注意dp的初始化 import java.util.*; public class Main{     static int maxValue=0;     public static void main(String []args){         Scanner input=new Scanner(Syste...

最后一个点不知道为啥过不去，偷懒了一下 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);        &n...

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

同时维护最大最小，全是负数的时候额外考虑一下。 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);       &nbs...

动态规划，同时维护最长连续正数和最长连续负数 import java.util.*; public class Main{     public static void main(String []args){         Scanner input=new Scanner(System.in);       &nbsp...

动态规划+二分查找，状态转移公式跟普通的有所不同，用tail数组维护当前最长的公共子序列，如果arr[i]>当前tail[len-1],则tail[len++]=arr[i],dp[i]=len; 如果不成立，则通过二分查找到最小的大于等于arr[i]的位置，插入arr[i]（这样才可以保证后面的序列尽可能长），此时注意更新dp[i]为index+1，而不是len。最后通过逆向遍历的方式就可以找到符合题意的最长上升子序列 import java.util.*; public class Solution {  &...

动态规划 dp含义是以i-1结尾和j-1结尾的str能否用p去匹配。除了常规的动态规划之外，还要关注p中为*的情况， 当p中索引为j-1的元素为*时，考虑：j-2的元素与s[i-1]是否相等，不相等的话，那dp[i][j-1]肯定就是flase了，所以尽量去寻找dp[i][j-2],有true的希望，此时两个字符相当于空 j-2的元素与s[i-1]相等，只要满足一下任意一种都可以时true    dp[i][j-1]为true，此时*相当于没有（保留j-2的元素），dp[i][j-2]为true，此时两个字符串为空，dp[i-1][j],此时相当于*表示为前面的...

用上下界去判断二叉搜索树 import java.util.*; class TreeNode {     int val;     TreeNode left;     TreeNode right;     public TreeNode(int val){        &n...

本来想用bfs的但是只能ac6个点，剩下的提示超时。于是就采用了两遍dfs的方式，用hashmap<key,node>来存无向图，使用used或者hashset保证不往回走，不过这题好像不需要回溯used。 import java.util.*; /*  * public class Interval {  *   int start;  *   int end;  * }  */ pu...

排序方法，注意要去重 HashSet方法，先把所有元素放到Set里面，然后对于每一个元素做向下和向上查找，更新最大值。 import java.util.*; public class Solution {     /**      * max increasing subsequence      * @param arr int整型一维数组...