LeetCode刷题笔记之动态规划（三）

一、子序列/子数组问题

子序列：按原数组的顺序排列，不一定是原数组中的相邻元素组成的。即子序列可以是不连续的。
子数组：原数组中连续的几个元素组成的数组。

1. 300【最长递增子序列】

• 题目：
  给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
  子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
• 代码：

class Solution {public int lengthOfLIS(int[] nums) {//dp表示以数组中第i个元素为结尾的最长严格递增子序列的长度//dp[i] = max(dp[j])+1,其中nums[j]是nums[i]左边小于nums[i]的元素//dp[0] = 1int[] dp = new int [nums.length];dp[0] = 1;int max = 1;for(int i=1;i<nums.length;i++){int tmp = 0;for(int j=0;j<i;j++){if(nums[j]<nums[i]){tmp = Math.max(tmp,dp[j]);}}dp[i] = tmp + 1;max = Math.max(dp[i],max);}return max;}
}

2. 72【编辑距离】

• 题目： 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
  你可以对一个单词进行如下三种操作：
  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
• 代码：

class Solution {public int minDistance(String word1, String word2) {//两个字符串的操作，使用双指针，i指向word1，j指向word2//dp[i][j]表示由左向右操作到word1的第i个位置，word2的第j个位置需要的最少操作数。//dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)//dp[0][j] = j,dp[i][0] = iint m = word1.length();int n = word2.length();if(n==0) return m;if(m==0) return n;int[][] dp = new int [m+1][n+1];for(int i=0;i<=m;i++){dp[i][0] = i;}for(int i=0;i<=n;i++){dp[0][i] = i;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1.charAt(i-1)==word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = minDp(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;}}}return dp[m][n];}public int minDp(int a,int b,int c){int tmp = Math.min(a,b);tmp = Math.min(tmp,c);return tmp;}
}

3. 53【最大子数组的和】

• 题目： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
  子数组是数组中的一个连续部分。
• 代码：

class Solution {public int maxSubArray(int[] nums) {//dp[i]表示以nums[i]为结尾的最大子数组的和//dp[i] = max(dp[i-1]+nums[i],nums[i])//dp[0] = nums[0]int[] dp = new int [nums.length];dp[0] = nums[0];int max = nums[0];for(int i=1;i<nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);max = Math.max(dp[i],max);}return max;}
}

4. 674【最长连续自增序列】

• 题目： 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
  连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
• 代码：

//方法一：双指针
class Solution {public int findLengthOfLCIS(int[] nums) {//双指针法，固定左指针，移动右指针，//直到右指针所指元素不满足条件,将左指针指向右指针int i=0;int max = 1;for(int j=1;j<nums.length;j++){if(nums[j-1]<nums[j]){max = Math.max(max,j-i+1);}else{i = j;}}return max;}
}
//方法二：动态规划
class Solution {public int findLengthOfLCIS(int[] nums) {//dp[i]表示以第i个元素结尾的最长连续递增子序列的长度//dp[i]=1 or dp[i-1]+1//dp[0]=1int[] dp = new int[nums.length];dp[0] = 1;int max=1;for(int i=1;i<nums.length;i++){if(nums[i-1]<nums[i]){dp[i] = dp[i-1]+1;}else{dp[i] = 1;}max = Math.max(max,dp[i]);}return max;}
}

5. 718【最长重复子数组】

• 题目： 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度。
• 代码：

class Solution {public int findLength(int[] nums1, int[] nums2) {//dp[i][j]表示以nums1[i],nums2[j]结尾的最长的公共子数组长度//dp[i][j] = dp[i-1][j-1]+1 (nums1[i]==nums2[j])//dp[0][0] = 0(nums1[i-1]!=nums2[j-1]) or 1(nums1[i-1]==nums2[j-1])int n = nums1.length;int m = nums2.length;int[][] dp = new int[n][m];int max=0;for(int i=0;i<n;i++){if(nums1[i]!=nums2[0]){dp[i][0] = 0;}else{dp[i][0] = 1;}max = Math.max(dp[i][0],max);}for(int i=0;i<m;i++){if(nums1[0]!=nums2[i]){dp[0][i] = 0;}else{dp[0][i] = 1;}max = Math.max(dp[0][i],max);}for(int i=1;i<n;i++){for(int j=1;j<m;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;}
}

6. 1143【最长公共子序列】

• 题目： 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
  一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
  例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
  两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
• 代码：

class Solution {public int longestCommonSubsequence(String text1, String text2) {//dp[i][j]表示以text1[i],text2[j]为结尾的最长公共子序列长度//dp[i][j] = dp[i-1][j-1]+1(text1[i]==text2[j]) or//dp[i][j] = max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])//dp[i][0] = 0(text1[0]!=text2[0]) or 1(text1[0]==text2[0])//dp[0][i] = 0(text1[0]!=text2[0]) or 1(text1[0]==text2[0])int n = text1.length();int m = text2.length();int[][] dp = new int[n][m];boolean flag = false;for(int i=0;i<n;i++){if((text1.charAt(i) == text2.charAt(0))||flag==true){dp[i][0] = 1;flag = true;}else {dp[i][0] = 0;}}int max=0;if(flag){max = 1;}flag = false;for(int i=0;i<m;i++){if((text1.charAt(0)==text2.charAt(i))||flag==true){dp[0][i] = 1;flag = true;}else{dp[0][i] = 0;}   }for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(text1.charAt(i) == text2.charAt(j)){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = maxNum(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);}max = Math.max(max,dp[i][j]);}}return max;}public int maxNum(int a,int b,int c){int tmp = Math.max(a,b);return Math.max(tmp,c);}
}

7. 647【回文子串】

• 题目： 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
• 代码：

class Solution {public int countSubstrings(String s) {//dp[i][j]表示在substring(i,j+1)是否是回文串//dp[i][j] = true(s[i]==s[j]) or false(s[i]!=s[j])//因为i由i+1决定，j由j-1决定，所以需要从左下角开始遍历//dp[][0]=false or true,dp[n-1][]=false or trueint n = s.length();boolean[][] dp = new boolean[n][n];int ans = 0;for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=1){dp[i][j] = true;ans++;}else if(dp[i+1][j-1]){dp[i][j] = true;ans++;}}}}return ans;}
}

8. 5【最长回文子串】

• 题目： 给你一个字符串 s，找到 s 中最长的回文子串。
  如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
• 代码：

class Solution {public String longestPalindrome(String s) {//dp[i][j]表示substring(i,j+1)是否是回文串//dp[i][j] = true(s[i]==s[j]) or false(s[i]!=s[j])//dp[i][j] = true(s[i]==s[j] and j-i<=1 or dp[i+1][j-1])int n = s.length();boolean[][] dp = new boolean[n][n];int maxLen = 0;int index = 0;for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s.charAt(i) == s.charAt(j)){if(j-i<=1){dp[i][j] = true;}else if(dp[i+1][j-1]){dp[i][j] = true;}if(dp[i][j] && (maxLen < j-i+1)){maxLen = j-i+1;index = i;}}}}return s.substring(index,index+maxLen);}
}