300.最长递增子序列
看完题后的思路
dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度
dp[i]=dp[j]+1 j从i-1向0遍历,在所有nums[j]<nums[i]中dp[j]最大
初始化 dp[0]=1
代码
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length==0){
return 0;
}
int[] dp=new int[nums.length];
dp[0]=1;
for (int i = 1; i <nums.length ; i++) {
int j = i-1;
int max=-1;
for (; j >=0 ; j--) {
if (nums[j]<nums[i]&&dp[j]>max){
dp[i]=dp[j]+1;
max=dp[j];
}
}
if (max==-1){
dp[i]=1;
}
}
int max=0;
for (int i : dp) {
max=Math.max(i,max);
}
return max;
}
}
看完题解的改进
dp【i】=max(dp【i】,dp【j】+1) nums【j】<nums【i】
674. 最长连续递增序列
看完题后的思路
dp[i]=dp[i-1]+1 nums[i]>nums[i-1]
dp[i]=1 else
代码
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0]=1;
int max=1;
for (int i = 1; i <nums.length ; i++) {
if (nums[i]>nums[i-1]){
dp[i]=dp[i-1]+1;
}else {
dp[i]=1;
}
max=Math.max(dp[i],max);
}
return max;
}
718. 最长重复子数组
看完题后的思路
dp[i][j]: 包含以A[i]结尾与以B[j]结尾的公共序列的长度
dp[i][j]=dp[i-1][j-1]+1 A[i]=B[j] else =0
初始化
dp[0][j]= 0/1
dp[i][0]=0/1
代码
public int findLength(int[] nums1, int[] nums2) {
int m=nums1.length,n=nums2.length;
int max=0;
int[][] dp=new int[m][n];
for (int i = 0; i <n ; i++) {
if (nums1[0]==nums2[i]){
dp[0][i]=1;
}else {
dp[0][i]=0;
}
max=Math.max(dp[0][i],max);
}
for (int i = 0; i <m ; i++) {
if (nums2[0]==nums1[i]){
dp[i][0]=1;
}else {
dp[i][0]=0;
}
max=Math.max(dp[i][0],max);
}
// 核心
for (int i = 1; i <m ; i++) {
for (int j = 1; j <n ; j++) {
if (nums1[i]==nums2[j]){
dp[i][j]=dp[i-1][j-1]+1;
}else {
dp[i][j]=0;
}
max=Math.max(dp[i][j],max);
}
}
return max;
}