典型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
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
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
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
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
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
空间优化：