给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
1）动态规划dp[i]--------到i为止包括i递增子序列的长度，最后一位必须包括nums[i]
dp[i]=Math.max(dp[0],dp[1],....,dp[i-1])+1;
if(nums[i]>nums[j]) dp[i]=Math.max(dp[i],dp[j]+1);
public int lengthOfLIS(int[] nums) {
if (nums.length==1) return 1;
int[] dp=new int[nums.length];
int result=1;
for(int i=0;inums[j]) dp[i]=Math.max(dp[i],dp[j]+1);}
if(dp[i]>result) result=dp[i];
}
return result;}
2) 贪心
思路：上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小
维护数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值，用len 记录目前最长上升子序列的长度，起始时 len为 1，d[1]=nums[0]。
注意：d[i] 是关于i单调递增的。
依次遍历数组 nums ，并更新数组 d 和 len的值。如果nums[i]>d[len] 则更新 len = len + 1，否则在 d[1...len]中找满足d[i−1] 最后整个算法流程为： 设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到nums[i] 时： 如果nums[i]>d[len] ，则直接加入到 d 数组末尾，并更新len=len+1； 否则，在 d数组中二分查找，找到第一个比 nums[i] 小的数 d[k]，并更新 d[k+1]=nums[i]。 解题套路：dp[i][j]------>以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最⻓重复⼦数组⻓度为dp[i][j] 2)双指针法 以每个点为中心遍历,中心不是一位就是2位 思路： dp[i][j]----[i, j]范围内最⻓的回⽂⼦序列的⻓度为dp[i][j] if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2; //其实是从最后反推回来的：i要用到i+1;j是递增 欢迎分享，转载请注明来源：内存溢出class Solution {
//dp[i][j]->以下标i-1为结尾的A,和以下标j-1为结尾的B,最⻓重复⼦数组⻓度为dp[i][j]
public int findLength(int[] nums1, int[] nums2) {
//想要得到dp[nums1.length][nums2.length]
int[][] dp=new int[nums1.length+1][nums2.length+1];
dp[0][0]=0; int result=0;
for(int i=1;i<=nums1.length;i++){//i的定义
for(int j=1;j<=nums2.length;j++){
if(nums1[i-1]==nums2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>result) result=dp[i][j];}
}
return result;}
}
2.2）最⻓公共⼦序列
给定两个字符串
text1
和
text2
，返回这两个字符串的最⻓公共⼦序列的⻓度。
⼀个字符串的⼦序列是指这样⼀个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，
"ace"
是
"abcde"
的⼦序列，但
"aec"
不是
"abcde"
的⼦序列。两个字符串的「公共⼦序列」是这两个字符串所共同拥有的⼦序列。
若这两个字符串没有公共⼦序列，则返回
0
。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//想要得到dp[text1.length()][text2.length()]
int[][] dp=new int[text1.length()+1][text2.length()+1];
if(text1==null||text2==null||text1.length()<=0||text2.length()<=0)
return text1.length()<=0? text2.length():text1.length();
dp[0][0]=0;
for(int i=1;i<=text1.length();i++){
for(int j=1;j<=text2.length();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[text1.length()][text2.length()];
}
}
2.3) 不相交的线-----序列
我们在两条独⽴的⽔平线上按给定的顺序写下
A
和
B
中的整数。 现在，我们可以绘制⼀些连接两个数字 A[i]
和
B[j]
的直线，只要
A[i] == B[j]
，且我们绘制的直线不与任何其他连线（⾮⽔平线）相交。以这种⽅法绘制线条，并返回我们可以绘制的最⼤连线数
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp=new int[nums1.length+1][nums2.length+1];
dp[0][0]=0; int result=0;
for(int i=1;i<=nums1.length;i++){
for(int j=1;j<=nums2.length;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-1][j],dp[i][j-1]);
if(resultclass Solution {
public int numDistinct(String s, String t) {
int[][] dp=new int[s.length()+1][t.length()+1];
for(int i=0;iclass Solution {
public int minDistance(String word1, String word2) {
int[][] dp=new int[word1.length()+1][word2.length()+1];
for(int i=0;i<=word1.length();i++) dp[i][0]=i;
for(int j=0;j<=word2.length();j++) dp[0][j]=j;
for(int i=1;iclass Solution {
public int countSubstrings(String s) {
if (s == null || s.length()< 1) return 0;
int result=0;
boolean[][] dp=new boolean[s.length()][s.length()];
for(int i=s.length()-1;i>=0;i--){
for(int j=i;jclass Solution {
public int countSubstrings(String s) {
if (s == null || s.length()< 1) return 0;
int result=0;
for (int i = 0; i < s.length(); i++) {
result += extend(s, i, i, s.length()); // 以i为中⼼
result += extend(s, i, i + 1, s.length()); // 以i和i+1为中⼼
}
return result;}
public int extend(String s, int i, int j, int length) {
int res=0;
while(i>=0&&j
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加⼊ 并不能增加[i,j]区间回⽂⼦串的⻓度，那么分别加⼊s[i]、s[j]看看哪⼀个可以组成最⻓的回⽂⼦序列。
else dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp=new int[s.length()][s.length()];
for (int i = 0; i
微信扫一扫
支付宝扫一扫
评论列表（0条）