Frank's blogs

永远好奇

0%

动态规划（二）

发表于 更新于
本文字数： 8.5k 阅读时长 ≈ 16 分钟

Leetcode 343. 整数拆分

  • 此题也是使用动态规划，主要是分两种情况讨论
    • 将一个数字拆成a和b，b使用之前拆分的最大乘积
    • b不拆分，直接相乘
      class Solution {
      public:
          int integerBreak(int n) {
              vector<int> maxArr(n+1);
              maxArr[1] = 0;
              maxArr[2] = 1;
              for(int i = 3; i<=n; ++i)
              {
                  for(int j = 1; j<i; ++j)
                  {
                      maxArr[i] = max(j*maxArr[i-j], maxArr[i]); // 拆分
                      maxArr[i] = max(j*(i-j), maxArr[i]); // 不拆分，就两个数字算
                  }
              }
              return maxArr[n];
          }
      };

      Leetcode 718. 最长重复子数组

  • 递推，使用上一个位置的连续长度加上这个位置是否相等递推出这个位置的
  • 如果相等，就是到i-1,j-1位置为止的连续长度+1
    class Solution {
    public:
        
        int findLength(vector<int>& nums1, vector<int>& nums2) {
            vector<vector<int>> map(nums1.size(), vector<int>(nums2.size(), 0));
            int maxLen = 0;
            for(int i = 0; i<nums1.size(); ++i)
            {
                for(int j = 0; j<nums2.size(); ++j)
                {
                    if(nums1[i] == nums2[j]){
                        if(i == 0 || j == 0)
                        {
                            map[i][j] = 1;
                        }
                        else 
                        {
                            map[i][j] = map[i-1][j-1]+1;
                        }
                        maxLen = max(map[i][j], maxLen);
                    }
                }
            }
            return maxLen;
        }
    };

Leetcode 115. 不同的子序列

  • 因为是从s中找t，所以递归的主要顺序是t找到了哪个位置
  • 假如s的i位置与t的j相等，那么该位置的子字符串种类就是i-1和j-1位置位置+t到j位置时之前的种类之和
  • 不等的话，就继承s字符串在之前位置，j字符串在当前位置的种类数量
    class Solution {
    public:
        int numDistinct(string s, string t) {
            vector<vector<int>> map(s.size()+1, vector<int>(t.size()+1, 0));
            for(int i = 0; i<=s.size(); ++i)
            {
                map[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])
                    {
                        map[i][j]=(map[i-1][j-1]+map[i-1][j])%((int)1e9+7); // 此处就是求和t字符串到j位置的所有可能性（包括s字符串之前的可能性）
                    }
                    else 
                    {
                        map[i][j] = map[i-1][j];
                    }
                }
            }
            return map[s.size()][t.size()];
        }
    };

Leetcode 583. 两个字符串的删除操作

  • 从i-1和j-1递推i和j

  • 当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

  • 那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

  • 因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

    • 因为对于dp[i][j-1]而言，就是第一个字符串到i-1位置和第二个字符串到j-2位置，第一个字符串增加一步删除就可以到i-2和j-2的位置，因此二者只差一步
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        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, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

Leetcode 72. 编辑距离

  • 此题遇上一个类似，只是增加了几个操作
    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], dp[i - 1][j], dp[i][j - 1]}) + 1;
                    }
                }
            }
            return dp[word1.size()][word2.size()];
        }
    };

Leetcode 1035. 不相交的线

  • 此题同样是类似的动态规划
  • 利用i-1和j-1推导i和j位置的值
  • 如果当前位置相等，此时则是在i-1和j-1位置的基础上+1
  • 因为递推的上一级是i-1和j-1，这就导致之前的连线最多只涉及之前的数字，不会于新加入的相交，从而防止了相交
    class Solution {
    public:
        int maxUncrossedLines(vector<int>& A, vector<int>& B) 
        {
            vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
            for (int i = 1; i <= A.size(); i++)
            {
                for (int j = 1; j <= B.size(); j++) 
                {
                    if (A[i - 1] == B[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[A.size()][B.size()];
        }
    };

Leetcode 1143. 最长公共子序列

  • 暴力递归方法（或者动态规划）
  • 每次两个字符串往前走一个位置（比如到达i, j），假如两个字符串在这个位置的值相同，那么就以(i-1, j-1)位置的最长子串的长度+1作为当前位置的值
  • 否则，就从两个字符串分别到（i-1，j）和（i，j-1）位置选择一个较大的作为结果
    • 这么做的关键原因（也就是遇上一题的区别）就是因为这个不必须是连续的
      class Solution {
      public:
          int longestCommonSubsequence(string text1, string text2) {
              int m = text1.length(), n = text2.length();
              vector<vector<int>> dp(m + 1, vector<int>(n + 1));
              for (int i = 1; i <= m; i++) {
                  char c1 = text1.at(i - 1);
                  for (int j = 1; j <= n; j++) {
                      char c2 = text2.at(j - 1);
                      if (c1 == c2) {
                          dp[i][j] = dp[i - 1][j - 1] + 1;
                      } else {
                          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                      }
                  }
              }
              return dp[m][n];
          }
      };

LeetCode 72. 编辑距离

  • 创建一个二维数组，一个维度是第一个字符串的长度，另一个是第二个字符串的长度
  • 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]
  • 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
  • 其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
    class Solution {
    public:
        int minDistance(string word1, string word2) {
            int m = word1.length();
            int n = word2.length();
            vector<vector<int>> map(m+1, vector<int>(n+1, INT_MAX));
            map[0][0] = 0;
            for(int i = 0; i<=m; ++i)
            {
                for(int j = 0; j<=n; ++j)
                {
                    
                    
                    if(i == 0&& j > 0)
                    {
                        map[i][j] = map[i][j-1]+1;
                    }
                    else if(i > 0&& j == 0)
                    {
                        map[i][j] = map[i-1][j]+1;
                    }
                    else if(i == 0 && j == 0)continue;
                    else if(word1[i-1] == word2[j-1])
                    {
                        map[i][j] = map[i-1][j-1];
                    }
                    else
                    {
                        map[i][j] = min(map[i-1][j], min(map[i][j-1], map[i-1][j-1]))+1;
                    }

                }
            }

            return map[m][n];
        }
    };

647. 回文子串

  • 注意循环顺序，从中间到两边，所以要从末端开始
    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]) {
                        if (j - i <= 1) { // 情况一 和 情况二
                            result++;
                            dp[i][j] = true;
                        } else if (dp[i + 1][j - 1]) { // 情况三
                            result++;
                            dp[i][j] = true;
                        }
                    }
                }
            }
            return result;
        }
    };

最长回文子序列

  • 此题大体与上面类似，唯一的区别是不需连续
  • 因此需要在条件不成立的时候使用dp[i][j] = max(dp[i+1][j], dp[i][j-1]);保存结果递推
    class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
            int result = INT_MIN;
            for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
                for (int j = i; j < s.size(); j++) {
                    if (s[i] == s[j]) {
                        if (j - i <= 1) 
                        { 
                            // 情况一 和 情况二
                            dp[i][j] = j-i+1;
                            result = max(result, dp[i][j]);
                        } 
                        else
                        {
                            dp[i][j] = dp[i+1][j-1]+2;
                            result = max(result, dp[i][j]);
                        }
                    }
                    else 
                    {
                        dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                    }
                }
            }
            return result;
        }
    };

Leetcode 673. 最长递增子序列的个数

  • 链接
  • 这道题目我们要一起维护两个数组。
  • dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
  • count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]
  • 那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。
  • 那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。
  • 在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。
  • 那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];
  • 注意初始化为1
    class Solution {
    public:
        int findNumberOfLIS(vector<int>& nums) {
            if (nums.size() <= 1) return nums.size();
            vector<int> dp(nums.size(), 1);
            vector<int> count(nums.size(), 1);
            int maxCount = 0;
            for (int i = 1; i < nums.size(); i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        if (dp[j] + 1 > dp[i]) {
                            dp[i] = dp[j] + 1;
                            count[i] = count[j];
                        } else if (dp[j] + 1 == dp[i]) {
                            count[i] += count[j];
                        }
                    }
                    if (dp[i] > maxCount) maxCount = dp[i];
                }
            }
            int result = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (maxCount == dp[i]) result += count[i];
            }
            return result;
        }
    };

小总结

  • 从大序列中找小序列的问题，假如是连续序列的话，不满足对应的条件的时候可以不处理
  • 但是假如不是连续序列的话，往往需要类似于dp[i][j] = max(dp[i+1][j], dp[i][j-1]);的操作来保存递推结果

Leetcode 486. 预测赢家

  • 此题使用起始和结束位置作为两个坐标的二维数组动态规划
  • 记忆化搜索的递归(原题)
    #include <iostream>
    #include <vector>
    #include <cstdlib>

    using namespace std;

    vector<vector<int>> res;

    int traversal(vector<int>& arr, int beg, int end)
    {
        // cout<<'!';
        if(beg>end || beg>=arr.size() || end<0)return 0;
        else if(beg == end)return arr[beg];
        if(res[beg][end]>=0)return res[beg][end];
        int ret = max(arr[beg]+min(traversal(arr, beg+1, end-1), traversal(arr, beg+2, end)),
            arr[end]+min(traversal(arr, beg+1, end-1), traversal(arr, beg, end-2)));
        res[beg][end] = ret;
        return ret;
    }

    int main()
    {
        int cnt;
        cin>>cnt;
        res = vector<vector<int>>(cnt, vector<int>(cnt, -1));
        int sum = 0;
        vector<int> arr(cnt, 0);
        for(int i = 0; i<cnt; ++i)
        {
            cin>>arr[i];
            sum+=arr[i];
        }
        
        for(int i = 0; i<cnt; ++i)
        {
            res[i][i] = arr[i];
        }
        
        
        cout<<max(first, sum-first)<<endl;
    }
  • 动态规划的答案
  • dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）
    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            // dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）
            int dp[22][22] = {0};
            // 当i == j的时候，nums[i]就是dp[i][j]
            for (int i = 0; i < nums.size(); i++) {
                dp[i][i] = nums[i];
            }
            for(int i = nums.size() - 2; i >= 0; i--) {
                for (int j = i + 1; j < nums.size(); j++) {
                    dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1]));
                }
            }
            return dp[0][nums.size() - 1] >= 0;
        }
    };