leetcode 300 最长递增子序列
1.定义dp数组:dp[i]表示以nums[i]结尾的最长递增子序列的长度。
2.定义递推公式
dp[i] = max(dp[j] + 1, dp[i]) 因为dp[j] + 1中的dp[j]并非是在前一个已经加1的dp[j]的基础之上再加上1。若从初始状态加1,而dp[i]永远保持的是最大的状态,则dp[j] + 1肯定要小一些。
3.初始化
Arrays.fill(dp, 1);
4.遍历顺序
for(int i = 0; i < nums.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = max(dp[j] + 1, dp[i]) ;
}
}
}
5.最后再遍历一遍dp数组,返回其中的最大值。
public int lengthOfLIS(int[] nums) {
int res = 0;
//定义dp数组
int[] dp = new int[nums.length];
//初始化dp数组
Arrays.fill(dp, 1);
//定义递推公式以及遍历顺序
for(int i = 0; i < nums.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
//每更新一次dp[i]的值便与以前一个nums[i]结尾的数组的最长递增子序列的值比较一次
res = Math.max(res, dp[i]);
}
return res;
}
}
leetcode 674 最长连续递增序列
1.定义dp数组:dp[i]是以i结尾的数列中的最长连续递增序列;
2.递推公式:本题只需考虑当前元素及其前一个元素;
dp[i] = dp[i - 1] + 1
3.初始化
Arrays.fill(dp, 1);
4.遍历顺序
只需要一层for循环,循环变量从1开始;
5.最后再遍历一遍dp数组,返回其最大值。
public int findLengthOfLCIS(int[] nums) {
//特判
if(nums.length == 1){
return 1;
}
int res = 0;
//定义dp数组
int[] dp = new int[nums.length];
//初始化
Arrays.fill(dp, 1);
//递推公式以及遍历顺序
for(int i = 1; i < nums.length; i++){
if(nums[i] > nums[i - 1]){
dp[i] = dp[i - 1] + 1;
}
res = Math.max(res,dp[i]);
}
return res;
}
}
leetcode 718 最长重复子数组
1.定义dp数组
dp[i][j]:表示以num1[i - 1]和nums2[j - 1]为尾部的数组num1和nums2的最长重复子数组的长度。
初始化:将无意义的值赋值为0:dp[i][0] = 0; dp[0][j] = 0;其余的值也为0。
2.递推公式
if(nums[i - 1] == nums[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}
3.遍历顺序
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
}
}
4.返回值
每遍历完dp数组的一个值,便与result进行一次比较,选出较大的值赋给result。
public int findLength(int[] nums1, int[] nums2) {
int res = 0;
//定义dp数组
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
//初始化dp数组
for(int i = 0; i <= nums1.length; i++){
dp[i][0] = 0;
}
for(int j = 0; j <= nums2.length; j++){
dp[0][j] = 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;
}
if(dp[i][j] > res){
res = dp[i][j];
}
}
}
return res;
}
}
leetcode1143 最长公共子序列
本题与上一题的区别在于本题的公共子序列可以在两个数组中不连续。
1.定义dp数组
dp[i][j]表示nums1[0, i -1]与nums2[0, j - 1]两个数组中最长公共子序列的长度。
初始化:dp[i][0]与dp[0][j]的值没有意义,故初始化为0。
2.定义递推公式与遍历顺序
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]);
}
注意:dp数组的遍历顺序由递推公式的推导方向而得出。
3.最后返回dp[nums1.length][nums2.length]。
public int longestCommonSubsequence(String text1, String text2) {
//定义dp数组
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
//递推公式与遍历顺序
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()];
}
}
leetcode 1035 不相交的线
本题的思路完全与上一题一致。
public int maxUncrossedLines(int[] nums1, int[] nums2) {
//定义dp数组
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
//定义递推公式与遍历顺序:遍历顺序与递推公式的推导顺序有关
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]);
}
}
}
return dp[nums1.length][nums2.length];
}
}
leetcode 53 最大子序和
1.定义dp[i]:以nums[i]结尾的最大连续子序列的和。
2.递推公式
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
//定义dp数组
vector<int> dp(nums.size());
//初始化dp数组
dp[0] = nums[0];
//定义递推公式以及遍历顺序
for(int i = 1; i < nums.size(); i++){
dp[i] = dp[i - 1] + nums[i] > nums[i] ? dp[i - 1] + nums[i] : nums[i];
res = dp[i] > res ? dp[i] : res;
}
return res;
}
};
leetcode 392 判断子序列
本题思路与1143最长公共子序列基本一致,只是本题仅仅考虑在更长的字符串t中删除元素以和s匹配最长公共子序列。
故唯一的区别在于递推公式:
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = dp[i][j - 1]
}
public boolean isSubsequence(String s, String t) {
if(s.length() > t.length()){
return false;
}
//定义dp数组
int[][] dp = new int[s.length() + 1][t.length() + 1];
//递推公式与遍历顺序
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= t.length(); j++){
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = dp[i][j - 1];
}
}
}
if(dp[s.length()][t.length()] == s.length()){
return true;
}
return false;
}
}
leetcode115 不同的子序列
1.定义dp数组
dp[i][j]:表示以下标i - 1为结尾的字符串中拥有以下标j - 1为结尾的字符串作为子序列的个数。
2.递推公式以及初始化
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];
}
初始化:
dp[i][0] = 1;表示一直删除字符串s中的元素,当s为空字符串时,恰好包含1个空字符串t。
dp[0][j] = 0;因为空字符串中一定不会包含非空字符串。
dp[0][0] = 1;因为空字符串中一定包含1个空字符串。
3.返回值
return dp[s.length()][t.length()];
public int numDistinct(String s, String t) {
//定义dp数组
int[][] dp = new int[s.length() + 1][t.length() + 1];
//初始化
for(int i = 0; i <= s.length();i++){
dp[i][0] = 1;
}
//递推公式以及遍历顺序
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= t.length(); j++){
if(s.charAt(i - 1) == t.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];//相当于从s中删除1个元素后,再看其中有多少个子序列t
}
}
}
return dp[s.length()][t.length()];
}
}
leetcode 583 两个字符串的删除操作
解法1:
1.定义dp数组:dp[i][j]表示使以i - 1下标结尾的字符串与以j - 1下标结尾的字符串相同所需要的最少的操作次数。
2.递推公式与初始化
if(s.charAt(i - 1) == t.charAt(j - 1))则dp[i][j] = dp[i - 1][j - 1];
否则的话:dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2);
初始化:dp[i][0] = i, dp[0][j] = j。
3.返回值:return dp[s.length()][t.length()]
public int minDistance(String word1, String word2) {
//定义dp数组
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
//初始化dp数组
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; i <= word1.length(); i++){
for(int j = 1; j <= word2.length(); j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];//若对应下标位置处的字母相等,则将其去除与否均不影响最小操作次数
}else{
dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 2);
}
}
}
return dp[word1.length()][word2.length()];
}
}
解法2:
可以先求出两个字符串的最长公共子序列的长度,再s.length() + t.length() - 2 * 最长公共子序列的长度。
public int minDistance(String word1, String word2) {
//定义dp数组
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
//递推公式以及遍历顺序
for(int i = 1; i <= word1.length(); i++){
for(int j = 1; j <= word2.length(); j++){
if(word1.charAt(i - 1) == word2.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 word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
}
}
leetcode 72 编辑距离
1.定义dp数组
dp[i][j]表示使以下标i - 1位置结尾的字符串与以下标j - 1位置结尾的字符串相同的话所需要的最小操作次数。
2.递推公式以及遍历顺序
if(s.charAt(i - 1) == t.charAt(j - 1))则将对应位置的字母去掉与否都不会影响最终的最少操作次数,故dp[i][j] = dp[i - 1][j - 1];
否则,dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
因为将s的最后一个字母去掉后,其本身便对应1次操作;同理将t的最后一个字母去掉后也对应1次操作,或者将s与t其中之一的最后一个字母替换为另一个的字母而使其相同。
注意:删除操作和增添操作是一一对应的关系,故它们的操作次数一样,所以只需要递推其中之一即可。
3.初始化
dp[i][0] = i; dp[0][j] = j (这里可以将下标0理解为空字符串)
4.返回值
return dp[s.length()][t.length()] (因为这对应完整长度的s与t的最少操作次数)
public int minDistance(String word1, String word2) {
//定义dp数组
int[][] dp = new int[word1.length() + 1][word2.length() + 1];
//初始化dp数组
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; i <= word1.length(); i++){
for(int j = 1; j <= word2.length(); j++){
if(word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
}
}
}
return dp[word1.length()][word2.length()];
}
}
leetcode 647 回文子串
1.定义dp数组:dp[i][j]表示子串[i, j]是否是回文子串,是则记录true,否则记录false。
2.定义递推公式:
if(s.charAt(i) == s.charAt(j)),且j - i <= 1,则一定是回文子串。此时,result++;
若在此前提下,j - i > 1,则继续判断s.charAt(i + 1)是否等于s.charAt(j - 1),若是,则[i, j]是回文子串,dp[i][j]为true, result++。
3.定义遍历顺序
根据递推公式的推导顺序,遍历顺序应该是从下往上,从左往右。
for(int i = s.length() - 1; i >= 0; i–){
for(int j = i; j < s.length(); j++){}
}文章来源:https://www.toymoban.com/news/detail-819445.html
public int countSubstrings(String s) {
int result = 0;
//定义dp数组,默认初始化为false
boolean[][] dp = new boolean[s.length()][s.length()];
//定义递推公式以及遍历顺序,j始终大于等于i
for(int i = s.length() - 1; i >= 0; i--){
for(int j = i; j < s.length(); j++){
if(s.charAt(i) == s.charAt(j)){
if(j - i <= 1){
dp[i][j] = true;
result++;
}else{
if(dp[i + 1][j - 1] == true){
dp[i][j] = true;
result++;
}
}
}
}
}
return result;
}
}
leetcode 516 最长回文子串
本题与上一题的区别在于其回文子序列可以不连续。
1.定义dp数组:dp[i][j]表示子序列[i, j]的最长回文子串(可以不连续)的长度。
2.定义递推公式以及遍历顺序
if(s.charAt(i) == s.charAt(j)),则dp[i][j] = dp[i + 1][j - 1] + 2;
若上述条件不相等,则dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);其分别表示只考虑字符串的左边或只考虑字符串的右边,选出两者最大的。
遍历顺序根据递推公式是从下往上,从左到右。
for(int i = s.length() - 1; i >= 0; i–){
for(int j = i + 1; j < s.length(); j++){}//j必须从i + 1开始,才能保证[i, j]子序列的长度至少为2。因为dp[i][i]已经被初始化为1了。
}
3.最后返回dp[0][s.length() - 1]。文章来源地址https://www.toymoban.com/news/detail-819445.html
public int longestPalindromeSubseq(String s) {
//定义dp数组
int[][] dp = new int[s.length()][s.length()];
//初始化dp数组
for(int i = 0; i < s.length(); i++){
dp[i][i] = 1;//只有1个字符的子序列也是长度为1的回文子序列
}
//定义递推公式以及遍历顺序
for(int i = s.length() - 1; i >= 0; i--){
for(int j = i + 1; j < s.length(); j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i + 1][j - 1] + 2;
}else{
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][s.length() - 1];
}
}
到了这里,关于动态规划之最长递增子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!