ch10-of-programmercarl-4

C++ C 代码随想录 背包问题 动态规划
刷题
发布日期:   2022-04-19

1 不相交的线

1.1 题目描述

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

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

  • nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线（非水平线）相交。

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

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

示例1:

输入: nums1 = [1,4,2], nums2 = [1,2,4]
输出: 2
解释: 可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例2:

输入: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出: 3

示例3:

输入: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出: 2

1.2 思路

  其实这道题就是找公共子序列，和1143. 最长公共子序列是一样的。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int dp[m+1][n+1];
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        for(int r = 1; r <= m; ++r){
            for(int c = 1; c <= n; ++c){
                if(nums1[r-1] == nums2[c-1]){
                    dp[r][c] = dp[r-1][c-1] + 1;
                }else{
                    dp[r][c] = max(dp[r-1][c], dp[r][c-1]);
                }
                ans = max(ans, dp[r][c]);
            }
        }
        return ans;
    }
};
  • C 实现
int maxUncrossedLines(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int dp[nums1Size+1][nums2Size+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= nums1Size; i++){
        for(int j = 1; j <= nums2Size; j++){
            if(nums1[i-1] == nums2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[nums1Size][nums2Size];
}

2 最大子数组和

2.1 题目描述

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

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

示例1:

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

示例2:

输入: nums = [1]
输出: 1

示例3:

输入: nums = [5,4,-1,7,8]
输出: 23

2.2 思路

/analysis_of_question_and_solving_thought_here/

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        int ans = dp[0];
        for(int i = 1; i < n; ++i){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            ans = max(ans, dp[i]);
        }
        return dp[n-1];
    }
};
  • C 实现
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, ans = INT_MIN;
        for(int n: nums){
            sum += n;
            ans = max(ans, sum);
            if(sum <= 0){
                sum = 0;
            }
        }
        return ans;
    }
};

3 判断子序列

3.1 题目描述

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

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

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例1:

输入: s = “abc”, t = “ahbgdc”
输出: true

示例2:

输入: s = “axc”, t = “ahbgdc”
输出: false

3.2 思路

  找公共子序列，如果公共子序列的长度为s的长度时，说明s为t的子序列，返回true,否则返回false.

完整代码如下：

  • Cpp 实现
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int s_len = s.length(), t_len = t.length();
        if(s_len > t_len) return false;
        int dp[s_len+1][t_len+1];
        memset(dp, 0, sizeof(dp));
        int len = 0;
        for(int i = 1; i <= s_len; ++i ){
            for(int j = 1; j <= t_len; ++j){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
                len = max(dp[i][j], len);
            }
        }
        return len == s_len;
    }
};
  • C 实现
bool isSubsequence(char * s, char * t){
    int slen = strlen(s), tlen = strlen(t);
    if(slen == 0) return true;

    int index= 0;
    for(int i = 0; i < tlen; i++){
        if(s[index] == t[i]){
            index++;
            if(index == slen) return true;
        }
    }
    return false;
}

4 不同的子序列

4.1 题目描述

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

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

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

示例1:

输入: s = “rabbbit”, t = “rabbit”
输出: 3
解释: 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
$\underline{\text{rabb}}$b$\underline{\text{it}}$
$\underline{\text{ra}}$b$\underline{\text{bbit}}$
$\underline{\text{rab}}$b$\underline{\text{bit}}$

示例2:

输入: s = “babgbag”, t = “bag”
输出: 5
解释: 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
$\underline{\text{ba}}$b$\underline{\text{g}}$bag
$\underline{\text{ba}}$bgba$\underline{\text{g}}$
$\underline{\text{b}}$abgb$\underline{\text{ag}}$
ba$\underline{\text{b}}$gb$\underline{\text{ag}}$
babg$\underline{\text{bag}}$

4.2 思路

dp[i][j]的含义为：字符串s的前j个字符所组成的含有字符串t的前i个字符的子序列数量。

  • 第一步，找t的前1个字符即i = 1(此时下标为0)在字符串s中出现的次数，因而需要遍历字符串s，当遍历到的字符与t[0]相等时，说明找到相同的，而t[0]在s[0...j]出现的次数等同于t[0]在s[0...j-1]和s[j-1]出现的次数，因此有：dp[0][j] = dp[0][j-1] + 1.

  • 第二步，找t的前2个字符即i = 2在字符串s中出现的次数. 如何计算次数呢？我们已经找了前1个字符在s中出现的次数，因而只需判断t[1]与当前遍历到的字符作比较并在前边的基础进行更新即可。当找到t[1] == s[j-1]时，dp[i][j]就等于子串t[0,1]在s[0...j-1]中出现的次数和t[0,1]在s[0...j-2]中出现的次数总和，即dp[2][j] = dp[2][j-1] + dp[1][j-1]；否则子串只在s[0...j-1]中出现过，因而dp[2][j] = dp[2][j-1].

  • …

由上述得到状态转移方程为：

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int numDistinct(string s, string t) {
        int s_len = s.length(), t_len = t.length();
        if(s_len < t_len) return 0;
        
        int dp[t_len][s_len + 1];
        memset(dp, 0, sizeof(dp));
        for(int r = 0; r < t_len; ++r){
            for(int c = 1; c <= s_len; ++c){
                dp[r][c] = dp[r][c-1];
                if(t[r] == s[c-1]){
                    if(r == 0){
                        dp[r][c] += 1;
                    }else if(dp[r][c] < INT_MAX - dp[r-1][c-1]){
                        dp[r][c] += dp[r-1][c-1];
                    }
                }
            }
        }
        return dp[t_len-1][s_len];
    }
};
  • C 实现
int numDistinct(char * s, char * t){
    if(strlen(t) > strlen(s)) return 0;

    int slen = strlen(s), tlen = strlen(t);
    int dp[slen+1][tlen+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= slen; i++){
        dp[i][0] = 1;
    }
    for(int i = 1; i <= slen; i++){
        for(int j = 1; j <= tlen; j++){
            if(s[i-1] == t[j-1] && dp[i-1][j-1] < INT_MAX - dp[i-1][j]){
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[slen][tlen];
}

5 两个字符串的删除操作

5.1 题目描述

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

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

示例1:

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

示例2:

输入: word1 = “leetcode”, word2 = “etco”
输出: 4

5.2 思路

  求最长公共子序列的长度，然后直接计算两个字符串与该长度的差值的加和即可。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int minDistance(string word1, string word2) {
        int word1_len = word1.length(), word2_len = word2.length();
        int dp[word1_len+1][word2_len+1];
        memset(dp, 0, sizeof(dp));
        int len = 0;
        for(int i = 1; i <= word1_len; ++i ){
            for(int j = 1; j <= word2_len; ++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
                len = max(dp[i][j], len);
            }
        }
        return (word1_len + word2_len) - 2*len;
    }
};
  • C 实现
int minDistance(char * word1, char * word2){
    int len1 = strlen(word1), len2 = strlen(word2);
    int dp[len1+1][len2+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(word1[i-1] == word2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return len1+len2-2*dp[len1][len2];
}

6 编辑距离

6.1 题目描述

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

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

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例1:

输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例2:

输入: word1 = “intention”, word2 = “execution”
输出: 5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

6.2 思路

  dp[i][j]的含义：word2前i个字符和word1的前j个字符之间的最小编辑距离。

  • 当检测到word2的当前字符word2[i]和word1当前遍历到的字符word1[j]相等时，不需要进行操作，此时word2前i个字符和word1的前j个字符之间的最小编辑距离就等于此时word2前i-1个字符和word1的前j-1个字符之间的最小编辑距离，即dp[i][j] = dp[i-1][j-1]。

  • 当word2[i] != word1[j],此时涉及插入新字符、删去当前字符、改变当前字符三种操作（简称增、删、改）

    • 增：实际上就是在word1的当前位置后插入字符word2[i],这里的操作数为1, 此时 word2[i]就已经有了 ，剩下的操作其实就是word2前 i-1 个字符和word1的前j个字符之间的最小编辑距离，因而有dp[i][j] = dp[i-1][j]+1.

    • 删：将word1的当前位置上的字符word1[j]删去，这里的操作数为1, 但此时 word2[i]还是没有 ，因而求word2的前i个字符和word1的前j个字符之间的最小编辑距离就变成求word2的前 i 个字符和word1的前j-1个字符之间的最小编辑距离，即dp[i][j] = dp[i][j-1]+1.

    • 改：将word1的当前位置上的字符word1[j]修改为word2[i]，操作数为1；然后 word2[i]就已经有了 ，剩下的就是word2前 i-1 个字符和word1的前j-1个字符之间的最小编辑距离，即dp[i][j] = dp[i-1][j-1]+1

  • 由于我们希望找到最小编辑距离，因而如果需要进行修改，则应该取三种操作中编辑距离最少的操作。

综上所述，可以得到状态转移方程：

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length(), len2 = word2.length();
        int dp[len2+1][len1+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i <= len1; ++i){
            dp[0][i] = i;
        }
        for(int i = 1; i <= len2; ++i){
            dp[i][0] = i;
        }
        for(int r = 1; r <= len2; ++r){
            for(int c = 1; c <= len1; ++c){
                if(word1[c-1] == word2[r-1]){
                    dp[r][c] = dp[r-1][c-1];
                }else{
                    //依次为增、删、改
                    dp[r][c] = min({dp[r-1][c], dp[r][c-1], dp[r-1][c-1]}) + 1;
                }
            }
        }
        return dp[len2][len1];
    }
};
  • C 实现
int minDistance(char * word1, char * word2){
    int len1 = strlen(word1), len2 = strlen(word2);
    int dp[len2+1][len1+1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= len1; ++i){
        dp[0][i] = i;
    }
    for(int i = 1; i <= len2; ++i){
        dp[i][0] = i;
    }
    for(int r = 1; r <= len2; ++r){
        for(int c = 1; c <= len1; ++c){
            if(word1[c-1] == word2[r-1]){
                dp[r][c] = dp[r-1][c-1];
            }else{
                //依次为增、删、改
                dp[r][c] = fmin(fmin(dp[r-1][c], dp[r][c-1]), dp[r-1][c-1]) + 1;
            }
        }
    }
    return dp[len2][len1];
}

7 回文子串

7.1 题目描述

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

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

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

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

示例1:

输入: s = “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”

示例2:

输入: s= “aaa”
输出: 6
解释: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

7.2 思路

  dp[i][j]的含义为：表明起点为i、终点为j的子串是否为回文串，如果是则置为true，否则为false.

  • 当s[i] != s[j]: 此时以i为起点、j为终点的子串不是回文串，因而dp[i][j] = false
  • 当s[i] == s[j]: 有可能是回文串，也有可能不是回文串，需要逐步往中间进行判断，可以分为下面三种情况：
      1. 当i == j时，此时子串仅有一个字符，因而必定为回文串，因此dp[i][j] = true;
      1. 当i == j-1时，此时子串有两个字符，且二者相等，如aa，此时也为回文串，因此dp[i][j] = true;
      1. 当i < j-1时，此时子串中有若干个字符，需要往中间判断，如果按照一般的回文串判断，则需要一个循环来判断，当头尾相等则头尾指针往中间移动一格直至相等说明该子串为回文串。动态规划则是利用之前的结果来进行判断：如果s[i] == s[j], 我们需要判断s[i+1...j-1]是否为回文串，即起点为i+1、终点为j-1的子串是否为回文串，根据dp的定义，这其实就是dp[i+1][j-1]，因此只需要判断dp[i+1][j-1]是否为true即可。

  注意，由于需要用到dp[i+1][j-1]， 即下一列的结果，因而需要从后往前遍历。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int countSubstrings(string s) {
        int len = s.length();
        bool dp[len][len];
        memset(dp, false, sizeof(dp));
        int ans = 0;
        for(int i = len-1; i >= 0; --i){
            for(int j = i; j < len; ++j){
                if(s[i] == s[j]){
                    if(j-i <= 1||dp[i+1][j-1]){
                        dp[i][j] = true;
                        ans += 1;
                    }
                }
            }
        }
        return ans;
    }
};
  • C 实现
int countSubstrings(char * s){
    int len = strlen(s);
    bool dp[len][len];
    memset(dp, false, sizeof(dp));
    int ans = 0;
    for(int i = len-1; i >= 0; --i){
        for(int j = i; j < len; ++j){
            if(s[i] == s[j]){
                if(j-i <= 1||dp[i+1][j-1]){
                    dp[i][j] = true;
                    ans += 1;
                }
            }
        }
    }
    return ans;
}

8 最长回文子序列

8.1 题目描述

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

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

示例1:

输入: s = “bbbab”
输出: 4
解释: 一个可能的最长回文子序列为 “bbbb” 。

示例2:

输入: s = “cbbd”
输出: 2
解释: 一个可能的最长回文子序列为 “bb” 。

8.2 思路

和上一题有点类似，dp[i][j]的含义为：字符串s的以i为头、j为尾的连续子串中的最长回文子序列长度，即子串s[i...j]的最长回文子序列长度。

  • 当i == j时当前子串长度为1必定为回文串，因此有dp[i][j] = 1.
  • 当头尾相等时，目前的最长回文子序列长度最少就为2了，现在我们需要对中间进行判断，即由求子串s[i...j]的最长回文子序列长度转化为求子串s[i+1...j-1]的最长回文子序列长度。由dp的定义，则后者其实就是dp[i+1][j-1]，因而有：dp[i][j] = dp[i+1][j-1] + 2.
  • 当头尾不相等时，s[i...j]的最长回文子序列长度就为s[i...j-1]和s[i+1...j]中的大者，即dp[i][j] = max(dp[i][j-1], dp[i+1][j]).

与上一题一样，都需要用到dp[i+1][j], 因而遍历顺序应该由后而前。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        int dp[len][len];
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < len; ++i){
            dp[i][i] = 1;
        }
        for(int i = len-1; i >= 0; --i){
            for(int j = i+1; j < len; ++j){
                if(s[i] == s[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[0][len-1];
    }
};
  • C 实现
int longestPalindromeSubseq(char * s){
    int len = strlen(s);
    int dp[len][len];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < len; ++i){
        dp[i][i] = 1;
    }
    for(int i = len-1; i >= 0; --i){
        for(int j = i+1; j < len; ++j){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1] + 2;
            }else{
                dp[i][j] = fmax(dp[i][j-1], dp[i+1][j]);
            }
        }
    }
    return dp[0][len-1];
}

总结

文章作者: Vyron Su
文章链接: http://example.com/2022/04/19/ch10-of-programmercarl-4/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 背包问题 动态规划