字数统计: 4.8k字   |   阅读时长: 22分

动态规划-4

300. 最长递增子序列 - 力扣（LeetCode）

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

动规五部曲：

  1. dp[i]的定义：dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

  2. 状态转移方程：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

    所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

    注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

  3. dp[i]的初始化：每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是1.

  4. 遍历顺序：dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。

    j其实就是0到i-1，遍历i的循环在外层，遍历j则在内层：

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        if(nums.size() == 1) return 1;
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for(int i = 1; i < nums.size();i++)
        {
            for(int j = 0; j <= i; j++)
            {
                if(nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
            }
            if(dp[i] > result)
            result = dp[i];
        }
        return result;
    }
};

674. 最长连续递增序列 - 力扣（LeetCode）

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

  1. 确定dp数组（dp table）以及下标的含义:dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
  2. 确定递推公式:dp[i + 1] = dp[i] + 1;
  3. 初始化：所以dp[i]应该初始1;
  4. 循环顺序：正序，从前到后一层循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if(nums.size() < 1) return 0;
        if(nums.size() == 1) return 1;
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for(int i = 1; i < nums.size();i++)
        {
            if(nums[i] > nums[i - 1])
            dp[i] = dp[i - 1] + 1;
            if(dp[i] > result)
            result = dp[i];
        }
        return result;
    }
};

718. 最长重复子数组 - 力扣（LeetCode）

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

1
2
3
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

动规五部曲：

  1. dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
  2. 即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
  3. dp[i][0] 和dp[0][j]初始化为0。
  4. 外层for循环遍历A，内层for循环遍历B。
  5. 举例推导dp数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for(int i = 1; i <= nums1.size(); i++)
        {
            for(int j = 1; j <= nums2.size(); 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;
    }
};

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

1
2
3
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

  1. dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

  2. 主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

    如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

  3. test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;

  4. 从递推公式，可以看出，有三个方向可以推出dp[i][j]

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1, vector<int> (text2.size() + 1, 0));
        for(int i = 1; i <= text1.size(); i++)
        {
            for(int j = 1; j <= text2.size(); j++)
            {
                if(text1[i - 1] == text2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

1035. 不相交的线 - 力扣（LeetCode）

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

  • nums1[i] == nums2[j]

  • 且绘制的直线不与任何其他连线（非水平线）相交。

    请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

本质上与1143. 最长公共子序列 - 力扣（LeetCode）一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size() + 1, vector<int> (nums2.size() + 1, 0));
        for(int i = 1; i <= nums1.size(); i++)
        {
            for(int j = 1; j <= nums2.size(); j++)
            {
                if(nums1[i - 1] == nums2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

53. 最大子数组和 - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

动规五部曲：

  1. dp[i]表示下标为i之前的连续子数组最大和。
  2. 递归公式：dp[i] = max(dp[i - 1] + nums[i] , nums[i])
  3. 初始化：dp[0] = nums[0]
  4. 遍历顺序：从前到后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector <int> dp(nums.size() , 0);
        dp[0] = nums[0];
        int result = dp[0];
        for(int i = 1; i < nums.size(); i++)
        {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if(dp[i] > result)
            result = dp[i];
        }
        return result;
    }
};

392. 判断子序列 - 力扣（LeetCode）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

1
2
输入：s = "abc", t = "ahbgdc"
输出：true

  1. 确定dp数组（dp table）以及下标的含义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

  2. if (s[i - 1] == t[j - 1])：t中找到了一个字符在s中也出现了。那么dp[i][j] = dp[i - 1][j - 1] + 1;

    if (s[i - 1] != t[j - 1])：相当于t要删除元素，继续匹配。dp[i][j] = dp[i][j - 1];

  3. 初始化dp[i][0]和dp[0][j]都应该是0.

  4. 遍历顺序：从上到下，从左到右

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector <vector<int>> dp(s.size() + 1, vector<int> (t.size() + 1, 0));
        for(int i = 1; i <= s.size(); i++)
        {
            for(int j = 1; j <= t.size(); j++)
            {
                if(s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                dp[i][j] = dp[i][j - 1];//相当于从s中取得元素数不变，增加t的下标，dp数组不变
            }
        }
        if(dp[s.size()][t.size()] == s.size())
        return true;
        else
        return false;
    }
};

115. 不同的子序列 - 力扣（LeetCode）

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

1
2
3
4
5
6
7
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

  1. 确定dp数组（dp table）以及下标的含义：dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

  2. 递推公式：当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

    当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]

  3. 初始化：那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。那么dp[0][j]一定都是0，s如论如何也变成不了t。

  4. dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的。

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numDistinct(string s, string t) {
        vector <vector<uint64_t>> dp(s.size() + 1, vector <uint64_t>(t.size() + 1, 0));//注意这里用是uint64_t类型，实际上它是long long int的别名，这里如果用int会有 runtime error: signed integer overflow: 1474397256 + 891953512 cannot be represented in type 'int'的报错。
        for(int i = 0; i <= s.size(); i++)
        dp[i][0] = 1;
        for(int i = 1; i <= s.size(); i++)
        {
            for(int j = 1; j <= t.size(); j++)
            {
                if(s[i - 1] == t[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[s.size()][t.size()];
    }
};

583. 两个字符串的删除操作 - 力扣（LeetCode）

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

1
2
3
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

  1. 确定dp数组（dp table）以及下标的含义：dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

  2. 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

    当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

    情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

    情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

    情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

  3. dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i，dp[0][j] = j。

  4. dp[i][j]都是根据左上方、正上方、正左方推出来的。

  5. 举例推导dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector <vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 0; i <= word1.size(); i++)
        dp[i][0] = i;
        for(int j = 0; j <= word2.size(); j++)
        dp[0][j] = j;
        for(int i = 1; i <=word1.size(); i++)
        {
            for(int j = 1; j <= word2.size(); j++)
            {
                if(word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
                else
                dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2));
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
1
2
3
4
5
6
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

动规五部曲：

  1. 确定dp数组（dp table）以及下标的含义：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

  2. 递推公式：if (word1[i - 1] == word2[j - 1])， 那么说明不用任何编辑，dp[i][j]就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

    if (word1[i - 1] != word2[j - 1])，此时就需要编辑了

  • 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

​ 即 dp[i][j] = dp[i - 1][j] + 1;

  • 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

​ 即 dp[i][j] = dp[i][j - 1] + 1;

​ word2添加一个元素，相当于word1删除一个元素

  • 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。
  1. 初始化：dp[i][0] = i，dp[0][j] = j。
  2. dp[i][j]都是根据左上方、正上方、正左方推出来的。
  3. 举例推导dp数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector <vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for(int i = 0; i <= word1.size(); i++)
        dp[i][0] = i;
        for(int j = 0; j <= word2.size(); j++)
        dp[0][j] = j;
        for(int i = 1; i <=word1.size(); i++)
        {
            for(int j = 1; j <= word2.size(); j++)
            {
                if(word1[i - 1] == word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
                else
                dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

647. 回文子串 - 力扣（LeetCode）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

1
2
3
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

  1. 确定dp数组（dp table）以及下标的含义:布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

  2. s[i]与s[j]不相等，dp[i][j]为false。

    当s[i]与s[j]相等时，有如下三种情况

    • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
    • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
    • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

  3. 初始化：全部为false

  4. 遍历顺序：dp[i][j]从dp[i + 1][j - 1]中推出，因此应该从下到上，从左到右。

  5. 模拟dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool> (s.size(), false));
        int result = 0;
        for(int i = s.size() - 1; i >= 0; i--)
        {
            for(int j = i; j < s.size(); j++)
            {
                if(s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]))
                {
                    dp[i][j] = true;
                    result++;
                }
            }
        }
        return result;
    }
};

516. 最长回文子序列 - 力扣（LeetCode）

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

1
2
3
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

动规五部曲：

  1. dp[i][j]含义：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

  2. 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

    如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

    • 加入s[j]的回文子序列长度为dp[i + 1][j]。

    • 加入s[i]的回文子序列长度为dp[i][j - 1]。

    • 那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

  3. 初始化为0，当i与j相等时dp[i][j]为1

  4. 遍历顺序：从下到上，从左到右。

  5. 模拟dp数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for(int i = 0; i < s.size(); i++)
        dp[i][i] = 1;
        for(int i = s.size() - 1; i >= 0; i--)
        {
            for(int j = i + 1; j < s.size(); j++)
            {
                if(s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][s.size() - 1];
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊