Home
  • 计算机网络
  • 操作系统
  • 数据结构与算法
  • 设计模式
  • JavaSE
  • JVM
  • JUC
  • Netty
  • CPP
  • QT
  • UE
  • Go
  • Gin
  • Gorm
  • HTML
  • CSS
  • JavaScript
  • vue2
  • TypeScript
  • vue3
  • react
  • Spring
  • SpringMVC
  • Mybatis
  • SpringBoot
  • SpringSecurity
  • SpringCloud
  • Mysql
  • Redis
  • 消息中间件
  • RPC
  • 分布式锁
  • 分布式事务
  • 个人博客
  • 弹幕视频平台
  • API网关
  • 售票系统
  • 消息推送平台
  • SaaS短链接系统
  • Linux
  • Docker
  • Git
GitHub (opens new window)
Home
  • 计算机网络
  • 操作系统
  • 数据结构与算法
  • 设计模式
  • JavaSE
  • JVM
  • JUC
  • Netty
  • CPP
  • QT
  • UE
  • Go
  • Gin
  • Gorm
  • HTML
  • CSS
  • JavaScript
  • vue2
  • TypeScript
  • vue3
  • react
  • Spring
  • SpringMVC
  • Mybatis
  • SpringBoot
  • SpringSecurity
  • SpringCloud
  • Mysql
  • Redis
  • 消息中间件
  • RPC
  • 分布式锁
  • 分布式事务
  • 个人博客
  • 弹幕视频平台
  • API网关
  • 售票系统
  • 消息推送平台
  • SaaS短链接系统
  • Linux
  • Docker
  • Git
GitHub (opens new window)
  • 哈希表

  • 双指针

  • 数组

  • 字符串

  • 链表

  • 树

  • 回溯

  • 动态规划

    • 典型问题—斐波那契类型
    • 典型dp—背包问题
    • 典型dp—子序列问题
      • 最长子序列问题
        • 300. 最长递增子序列
        • 674. 最长连续递增序列
        • 673. 最长递增子序列的个数
        • 435. 无重叠区间
        • 646. 最长数对链
        • 1218. 最长定差子序列
        • 1027. 最长等差数列
        • 873. 最长的斐波那契子序列的长度
        • 354. 俄罗斯套娃信封问题
        • 2770. 达到末尾下标所需的最大跳跃次数
        • 368. 最大整除子集
        • 413. 等差数列划分
        • 446. 等差数列划分 II
        • 689. 三个无重叠子数组的最大和
        • 960. 删列造序 III
        • 1691. 堆叠长方体的最大高度
        • 1626. 无矛盾的最佳球队
      • 公共子序列问题
        • 1143. 最长公共子序列
        • 115. 不同的子序列
        • 392. 判断子序列
        • 718. 最长重复子数组
        • 583. 两个字符串的删除操作
        • 72. 编辑距离
        • 712. 两个字符串的最小ASCII删除和
        • 1035. 不相交的线
    • 典型dp—股票问题
    • 线性dp
    • 区间dp
    • 树形dp
    • 状压dp
    • 数位dp
    • 多维dp
  • 图

  • 二分查找

  • 贪心

  • 栈&队列

  • 堆

  • 位运算

  • 数据结构设计

  • rui的精选题单

  • 笔试真题

  • LeetCode周赛

  • ACM模式输入输出
  • 数学

  • 数据结构与算法
  • 动态规划
Nreal
2023-11-17
目录

典型dp—子序列问题

# 最长子序列问题

# 300. 最长递增子序列 (opens new window)

方法一:记忆化搜索

class Solution {
    int[] nums;
    int[] memo;
    public int lengthOfLIS(int[] nums) {
        int ret = 0;
        int n = nums.length;
        this.nums = nums;
        this.memo = new int[n];
        for(int i=0;i<n;i++){
            ret = Math.max(ret,dfs(i));
        }
        return ret;
    }
    int dfs(int i){
        if(memo[i]!=0){
            return memo[i];
        }
        for(int j=0;j<i;j++){
            if(nums[j]<nums[i]){
                memo[i] = Math.max(memo[i],dfs(j));
            }
        }
        return ++memo[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二:动态规划

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ret = 0;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 674. 最长连续递增序列 (opens new window)

# 673. 最长递增子序列的个数 (opens new window)

# 435. 无重叠区间 (opens new window)

# 646. 最长数对链 (opens new window)

# 1218. 最长定差子序列 (opens new window)

# 1027. 最长等差数列 (opens new window)

# 873. 最长的斐波那契子序列的长度 (opens new window)

# 354. 俄罗斯套娃信封问题 (opens new window)

# 2770. 达到末尾下标所需的最大跳跃次数 (opens new window)

# 368. 最大整除子集 (opens new window)

# 413. 等差数列划分 (opens new window)

# 446. 等差数列划分 II (opens new window)

# 689. 三个无重叠子数组的最大和 (opens new window)

# 960. 删列造序 III (opens new window)

# 1691. 堆叠长方体的最大高度 (opens new window)

# 1626. 无矛盾的最佳球队 (opens new window)

# 公共子序列问题

# 1143. 最长公共子序列 (opens new window)

子问题:

  • s的前i-1个字母与t的前j-1个字母的LCS长度;
  • s的前i个字母与t的前j-1个字母的LCS长度;
  • s的前i-1个字母与t的前j个字母的LCS长度;

公共子序列递推公式:

dfs(i,j)=dfs(i-1,j-1)+1 s[i]=t[j];

dfs(i,j)=max(dfs(i-1,j),dfs(i,j-1)) s[i]≠t[j];

方法一:记忆化搜索

class Solution {
    char[] s,t;
    int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        this.s = text1.toCharArray();
        this.t = text2.toCharArray();
        int m = s.length;
        int n = t.length;
        this.memo = new int[m][n];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(m-1,n-1);
    }
    int dfs(int i,int j){
        if(i<0 || j<0)
            return 0;
        if(memo[i][j]!=-1)
            return memo[i][j];
        if(s[i]==t[j]){
            return memo[i][j] = dfs(i-1,j-1)+1;
        }else{
            return memo[i][j] = Math.max(dfs(i-1,j),dfs(i,j-1));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方法二:动态规划

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(text1.charAt(i)==text2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 115. 不同的子序列 (opens new window)

# 392. 判断子序列 (opens new window)

# 718. 最长重复子数组 (opens new window)

# 583. 两个字符串的删除操作 (opens new window)

# 72. 编辑距离 (opens new window)

dfs(i,j)=dfs(i-1,j-1) s[i]=t[j]

dfs(i,j)=min(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1))+1 s[i]≠t[j]

​ 删除 插入 替换

方法一:记忆化搜索

class Solution {
    int[][] memo;
    char[] s;
    char[] t;
    public int minDistance(String word1, String word2) {
        this.s = word1.toCharArray();
        this.t = word2.toCharArray();
        int m = s.length;
        int n = t.length;
        this.memo = new int[m][n];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(m-1,n-1);
    }
    int dfs(int i,int j){
        // 如果一个字符串已空,只能将另一个字符串全部删除
        if(i<0) return j+1;
        if(j<0) return i+1;
        if(memo[i][j]!=-1)
            return memo[i][j];
        if(s[i]==t[j])
            return memo[i][j] = dfs(i-1,j-1);
        else 
            return memo[i][j] = Math.min(dfs(i-1,j-1),Math.min(dfs(i-1,j),dfs(i,j-1)))+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

方法二:动态规划

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++)   
            dp[i][0] = i;
        for(int j=1;j<=n;j++)
            dp[0][j] = j;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i+1][j+1] = word1.charAt(i)==word2.charAt(j)?dp[i][j]:Math.min(Math.min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

空间优化:


1

# 712. 两个字符串的最小ASCII删除和 (opens new window)

# 1035. 不相交的线 (opens new window)

典型dp—背包问题
典型dp—股票问题

← 典型dp—背包问题 典型dp—股票问题→

Theme by Vdoing | Copyright © 2021-2024
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式