最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
示例 1：
**输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。
思路：利用动态规划
定义 dp[i][j]：text1 的前 i 个字符（即 text1[0..i-1]）和 text2 的前 j 个字符（即 text2[0..j-1]）的最长公共子序列长度。
目标： 返回 dp[m][n]，其中 m = text1.length()，n = text2.length()。
细节：dp里的i和j表示前i个和前j个，dp[i]对应text1[i-1]而不是text[i]
dp[0]表示前0个也就是空串
状态转移
对于 dp[i][j]，考虑 text1[i-1] 和 text2[j-1]：
情况 1：text1[i-1] == text2[j-1]
-
这两个字符可以加入公共子序列
-
dp[i][j] = dp[i-1][j-1] + 1
情况 2：text1[i-1] != text2[j-1]
-
这两个字符不能同时加入
-
取两种情况的最大值：
-
放弃
text1[i-1]：dp[i-1][j] -
放弃
text2[j-1]：dp[i][j-1]
-
-
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化
text
dp[0][j] = 0 （text1 为空，公共子序列长度为 0）
dp[i][0] = 0 （text2 为空，公共子序列长度为 0）
遍历顺序
-
外层循环：
i从 1 到 m -
内层循环：
j从 1 到 n
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++)dp[i][0]=0;
for(int i=0;i<=n;i++)dp[0][i]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}
else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
return dp[m][n];
}
}
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度
**输入：**nums = [10,9,2,5,3,7,101,18]
**输出：**4
**解释：**最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路：一维动态规划
dp[i]表示以nums[i]结尾的最长递增子序列长度
初始化dp[0…n-1]=1->任意一个数字能以自己为长度构建
i从1->n-1遍历 j从0->i-1
如果nums[j]<nums[i]->说明 nums[i] 可以接在 nums[j] 后面
更新dp[i]=max(dp[i],dp[j]+1);
class Solution {
public int lengthOfLIS(int[] nums) {
int n=nums.length;
int[] dp=new int[n];
int maxlen=1;
for(int i=0;i<n;i++)dp[i]=1;
for(int i=1;i<n;i++)
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
maxlen=Math.max(maxlen,dp[i]);
}
return maxlen;
}
}