最长回文子序列
定义dp[i][j]表示区间[i:j]字符组成的最长回文子序列
最长递增子序列
最长递增子序列
通过dp[i]维护以i结尾的最长递增子序列的长度
通过cnt[i]维护对应的最长递增子序列个数
如果对应的长度需要进行更新,将对应的cnt[i]置为cnt[j]
class Solution {
public int findNumberOfLIS(int[] nums) {
//通过两个数组维护对应的最长的递增子序列的长度,cnt[i]以对应的nums[i]结尾的元素的最长上升子序列的个数
int n=nums.length;
int[] dp=new int[n];
int[] cnt=new int[n];
Arrays.fill(dp,1);
Arrays.fill(cnt,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
//长度变化
if(dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
//对应的个数也变化
cnt[i]=cnt[j];
}else if(dp[j]+1==dp[i]){
//长度没有变化
cnt[i]+=cnt[j];
}
}
}
}
//首先找到最大长度
int maxv=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
maxv=Math.max(maxv,dp[i]);
}
int res=0;
for(int i=0;i<n;i++){
if(dp[i]==maxv){
res+=cnt[i];
}
}
return res;
}
}
最长递增子序列 贪心+二分 O(nlogn)
当前已经求出的最长上升子序列长度为len 初始时为1 从前往后遍历数组nums,当遍历到nums[i]时:
+ 如果严格大于nums[i]>d[len];直接加入数组d末尾,并更新数组长度len=len+1
+ 否则,在d数组进行二分查找,对于第一个小于nums[i]的元素位置k,并将的d[k+1]=nums[i];
+ 边界如果没有元素小于nums[i];即对于所有的最小元素d[1]>=nums[i],直接将d[1]更新为尽可能小d[1]=nums[i];否则更新d[k+1]=nums[i]
class Solution {
//贪心,需要递增子序列尽可能长,需要时序列上升尽可能慢
//通过贪心+二分的方式计算最长递增子序列
public static int lengthOfLIS(int[] nums){
int len=1;int n=nums.length;
if(n==0){
return 0;
}
int[] d=new int[n+1];
d[len]=nums[0];
for(int i=1;i<n;i++){
if(nums[i]>d[len]){//严格递增的子序列
d[++len]=nums[i];
}else{
//二分修改位置,找到第一个小于nums[i]的位置
int left=1;int right=len;
while (left < right) {
int mid=left+right+1>>1;
if(d[mid]<nums[i]){//找到第一个小于nums[i]的元素位置
left=mid;
}else{
right=mid-1;
}
}
if(d[1]>=nums[i]){//如果所有的元素都是大于等于nums[i]即不存在小于的元素
d[1]=nums[i];
}else{
d[left+1]=nums[i];
}
}
}
return len;
}
}
如果是非递减的子序列 可以取等号
修改三个地方:
+ 对于每一个元素判断是否nums[i]>=d[len] 可以取等号,直接将该元素加到d[++len]
+ 否则找到前面小于等于当前元素的位置 k 更新d[k+1]=nums[i];
+ 如果所有的元素都不小于等于nums[i] 即d[1]>nums[i] 直接将d[1]更新为更小 d[1]=nums[i];
public int findLIS(int[] arr,int start,int k){
//最长递增子序列长度为arr.length/k+10
int[] nums=new int[arr.length/k+10];
nums[1]=arr[start];
int len=1;
for(int i=start+k;i<arr.length;i+=k){
if(arr[i]>=nums[len]){
nums[++len]=arr[i];
}else{
//二分
int left=1;int right=len;
while (left < right) {
int mid=left+right+1>>1;
if(nums[mid]<arr[i]){
left=mid;
}else{
right=mid-1;
}
}
if(nums[1]>=arr[i]){
nums[1]=arr[i];
}else{
nums[left+1]=arr[i];
}
}
}
return len;
}
应用: 使数组k递增的最少操作次数
使数组k递增的最少操作次数
k递增等价于将原数组分为k个子序列,要求每一个子序列非递减
逆向就是计算每一个子序列最长递增(非递减)子序列;n-k个子序列最长递增子序列长度之和
class Solution {
public int kIncreasing(int[] arr,int k){
int res=arr.length;
//减去每一小组最长递增子序列
for(int i=0;i<k;i++){
res-=findLIS(arr,i,k);
}
return res;
}
public int findLIS(int[] arr,int start,int k){
//最长递增子序列长度为arr.length/k+10
int[] nums=new int[arr.length/k+10];
nums[1]=arr[start];
int len=1;
for(int i=start+k;i<arr.length;i+=k){
if(arr[i]>=nums[len]){
nums[++len]=arr[i];
}else{
//二分
int left=1;int right=len;
while (left < right) {
int mid=left+right+1>>1;
if(nums[mid]<=arr[i]){
left=mid;
}else{
right=mid-1;
}
}
if(nums[1]>arr[i]){
nums[1]=arr[i];
}else{
nums[left+1]=arr[i];
}
}
}
return len;
}
}
找出每一个位置为止最长的最长递增子序列 二分 贪心 数组模拟栈
class Solution {
public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
int n=obstacles.length;
int[] res=new int[n];
int[] stack=new int[n];
int top=-1;
for(int i=0;i<n;i++){
if(top==-1||obstacles[i]>=stack[top]){
stack[++top]=obstacles[i];
res[i]=top+1;
}else{
//二分之前单调递增数组第一个大于当前元素 替换
int left=0;int right=top;
while (left < right) {
int mid=left+right>>1;
if(stack[mid]>obstacles[i]){
right=mid;
}else{
left=mid+1;
}
}
stack[left]=obstacles[i];
res[i]=left+1;
}
}
return res;
}
}
最长公共子序列
最长公共子序列
给定两个数组,将两个数组中相等元素连线,求最多不相交的线
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int n=nums1.length;int m=nums2.length;
int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(nums1[i-1]==nums2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[n][m];
}
}
奇怪的打印机
定义dp[i][j]表示打印区间[i:j]字符最少次数
如果str[i]==str[j] dp[i][j]=dp[i][j-1]
如果str[i]!=str[j] dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1]);
将比较长的段分成若干小段
class Solution {
public int strangePrinter(String s){
int n=s.length();
int[][] dp=new int[n][n];
for(int i=0;i<n;i++){
Arrays.fill(dp[i],Integer.MAX_VALUE);
}
for(int i=0;i<n;i++){
dp[i][i]=1;
}
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=dp[i][j-1];
}else{
for(int k=i;k<j;k++){
dp[i][j]=Math.min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
return dp[0][n-1];
}
}