Flag敢立，才敢拔！

0%

算法之动态规划

发表于 更新于 分类于 ，
本文字数： 8.7k 阅读时长 ≈ 8 分钟

动态规划实在是同重要了，而且饱含了计算机之美，虽然多次被虐，但还是决定要认真牢记！

  • 主要思想：用空间换时间，从而避免递归中不必要的重复计算。
  • 难点：定义\(dp[i]\)的含义，以及动态转移方程

线性DP

1. 连续子数组最大和（存在负数）

  • 解题思路：
    • \(dp[i]:\) 定义为在前\(i\)个数中，以第\(i\)个数为结尾的子数组最大连续和
    • 动态转移方程：\(dp[i] = max(dp[i-1]+dp[i],\ dp[i])\) （如果到目前为止你的过去是负担，那就放下吧，每天都是新的开始~）
  • 代码： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #include<bits/stdc++.h>
    using namespace std;

    int main()
    {
        int n = 0;
        cin >> n;
        vector<long> A(n+10, 0); // notice the range of each value!
        for(int i=0; i<n; ++i) cin >> A[i];
        long sum_max = A[0];
        for(int i=1; i<n; ++i)
        {
            A[i] = max(A[i-1] + A[i], A[i]);
            sum_max = max(A[i], sum_max);
        }
        cout << sum_max << endl;
        return 0;
    }

2. 不相邻取数的子数组最大和（均为正数）

  • 解题思路：
    • \(dp[i]:\) 定义为在前\(i\)个数中，以第\(i\)个数为结尾的不相邻数的最大和
    • 动态转移方程：\(dp[i] = max(dp[i-2]+dp[i],\ dp[i-3]+dp[i])\) （只考虑\(a_i\)为正数的情况，需要求一堆数的max）
  • 代码： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include<bits/stdc++.h>
    using namespace std;

    int main()
    {
        int n;
        cin >> n;
        vector<long> A(n+10, 0);
        for(int i=0; i<n; ++i) cin >> A[i];
        long rst = A[0];
        if(n == 2)
        {
            rst = max(rst, A[1]);
        }
        else if(n >= 3)
        {
            A[2] = A[0]+A[2];
            rst = max(A[1], A[2]);
            for(int i=3; i<n; ++i)
            {
                // notice all the elems in A are positive number
                // otherwise need to max{A[i]+A[0],...,A[i]+A[i-2]}
                A[i] = max(A[i] + A[i-2], A[i] + A[i-3]); 
                rst = max(rst, A[i]);
            }
        }
        cout << rst << endl;
        return 0;
    }

3. 括号生成

  • 题目表述：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合

    1
    2
    输入：n = 3
    输出：["((()))","(()())","(())()","()(())","()()()"]

  • 动态规划解题思路：（同样可以用带回溯的递归来解题，后附代码）

    • \(dp[i]\)：表示当有 \(i\) 组括号时，可能的全部排列方式（字符串集合vector<string>）
    • 动态转移方程：dp[i] = for(j=0; j<i; ++j){第i个括号里有j组括号，右边有i-j-1组括号}
      • 第i组括号的左括号加在字符串最左边，右括号加在p，q之间，其中p和q分别是dp[j]和dp[i-j-1]内任意的数组，其中j可以从0取到i-1

  • 动归代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
        vector<string> generateParenthesis(int n) 
        {
            if(n == 0) return {};
            if(n == 1) return {"()"};
            vector<vector<string>> dp(n+1); // 这里是1维dp
            dp[0] = {""};
            dp[1] = {"()"};
            for(int i=2; i<=n; ++i)
            {
                for(int j=0; j<i; ++j)
                {
                    for(string p : dp[j])
                    {
                        for(string q : dp[i-j-1]) // 这里i就是n，n-j-1+j = n-1，即p+q是n-1组括号
                        {
                            dp[i].push_back("(" + p + ")" + q);
                        }
                    }
                }
            }
            return dp[n];
        }
    };

  • 带回溯的递归代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    class Solution {
    public:
        void generate(vector<string> & result, string & cur, int left, int right, int total)
        {
            if(cur.size() == total)
            {
                result.push_back(cur);
                return;
            }
            if(left < total/2)
            {
                cur.push_back('(');
                left++;
                generate(result, cur, left, right, total);
                cur.pop_back();
                left--;
            }
            if(right < left)
            {
                cur.push_back(')');
                right++;
                generate(result, cur, left, right, total);
                cur.pop_back();
                right--;
            }
            return;
        }
        vector<string> generateParenthesis(int n) {
            vector<string> result;
            string current;
            generate(result, current, 0, 0, 2*n); // 传入左右括号的个数
            return result;
        }
    };

4. 最长有效括号

  • 题目描述：给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

    1
    2
    3
    输入：s = "(()"
    输出：2
    解释：最长有效括号子串是 "()"

  • 解题思路：

    • dp[i]：表示以 s[i] 为结尾的最长有效子字符串的长度

    • 动态转移方程：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      if s[i] == '(' :
          dp[i] = 0
      if s[i] == ')' :
          # 为"(...)()"类型
          if s[i - 1] == '(' : 
              dp[i] = dp[i - 2] + 2 #要保证i - 2 >= 0
          # 为"(...)((...))"类型
          if s[i - 1] == ')' and s[i - dp[i - 1] - 1] == '(' :
              dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 #要保证i - dp[i - 1] - 2 >= 0

    • 初始化：全部为0（主要是dp[0]=0）

    • 求解：\(max_i\{dp[i]\}\)

  • 代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution {
    public:
        int longestValidParentheses(string s) 
        {
            int n = s.length();
            vector<int> dp(n, 0);
            int maxLen = 0;
            for(int i=1; i<n; ++i) // 第一个不管是什么，dp[0]都是1
            {
                if(s[i] == ')')
                {
                    if(s[i-1] == '(')
                    {
                        dp[i] = 2;
                        if(i-2 > 0) dp[i] = 2 + dp[i-2];
                    }
                    else if(dp[i-1] > 0) // 表示s[i-1]==')'且有匹配
                    {
                        if(i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1]=='(') // 判断边界
                        {
                            dp[i] = dp[i-1] + 2;
                            if(i-dp[i-1]-2 > 0)
                            {
                                dp[i] = dp[i] + dp[i-dp[i-1]-2]; // 判断边界
                            }
                        }
                    }
                }
                maxLen = max(maxLen, dp[i]);
            }
            return maxLen;
        }
    };

5. 接雨水

  • 题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

    1
    2
    3
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

  • 解题思路：

    1. 动归：
      • 部分利用动归，只是起到存储，不用重复计算的功能，本题用来计算节点 i 左侧的最大值（包括i）和右侧的最大值 maxLeft[i]和maxRight[i]
      • ans += min(maxLeft[i], maxRight[i]) - height[i] 遍历所有的i
    2. 双指针：
      • left和right指针分别从左右两侧向中间靠拢，maxLeft和maxRight分别记录当前左侧和右侧的最大值
      • 如果height[left]<height[right]时，则 i 位置的存雨量取决于左侧的最大值和当前高度差，即maxLeft-height[left] if(maxLeft>height[left])，如果左侧最大值小于当前高度，则只用更新maxLeft即可

  • 动归思想代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    class Solution {
    public:
        int trap(vector<int>& height) 
        {
            int ans = 0;
            int size = height.size();
            vector<int> maxLeft(size, 0), maxRight(size, 0);
            maxLeft[0] = height[0];
            for(int i=1; i<size; ++i)
            {
                maxLeft[i] = max(height[i], maxLeft[i-1]);
            }
            maxRight[size-1] = height[size-1];
            for(int i=size-2; i>=0; --i)
            {
                maxRight[i] = max(maxRight[i+1], height[i]);
            }

            for(int i=0; i<size; ++i)
            {
                ans += min(maxLeft[i], maxRight[i]) - height[i];
            }
            return ans;
        }
    };

  • 双指针思路代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution {
    public:
        int trap(vector<int>& height) 
        {
            int ans = 0;
            int size = height.size();
            int left = 0, right = size-1;
            int maxLeft = 0, maxRight = 0;
            while(left < right)
            {
                if(height[left] < height[right]) // 此时注水高度取决于左侧最高点
                {
                    if(maxLeft > height[left]) ans += maxLeft - height[left];
                    else maxLeft = height[left];
                    left++; // 注意无论ifelse，都需要++
                }
                else // 注水高度取决于右侧最高点
                {
                    if(maxRight > height[right]) ans += maxRight - height[right];
                    else maxRight = height[right];
                    right--; // 注意这里是--
                }
            }
            return ans;
        }
    };

[TOC]

二维DP

1. 最长回文子串（除DP外还有两种更优解法待学习！）

  • 题目描述：给你一个字符串 s，找到 s 中最长的回文子串。

    1
    2
    3
    4
    # 样例一
    输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。

  • 解题思路：

    • dp[i][j]​：表示从 s 的第 i 位到第 j 位是否为回文串
    • 动态转移方程：dp[i][j] = dp[i+1][j-1] && (s[i]==s[j])
    • 初始化：i==j 时，dp[i][i]=true; j-i=2时，dp[i][j] = (s[i]==s[j])

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    class Solution {
    public:
        string longestPalindrome(string s) 
        {
            if(s.size()<2) return s;
            
            vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
            int MaxLen = 1; // 初值为1
            int begin = 0;
            
            // 边界条件 
            for(int i=0; i<s.size(); ++i)
            {
                dp[i][i] = true;
            }

            for(int L=2; L<=s.size(); ++L)
            {
                for(int i=0; i<s.size(); ++i)
                {
                    int j = i+L-1;
                    if(j >= s.size()) continue;
                    if(s[i] != s[j])
                    {
                        dp[i][j] = false;
                    }
                    else
                    {
                        if(L == 2) dp[i][j] = true;
                        else dp[i][j] = dp[i+1][j-1]; // 动态转移方程
                    }
                    // 只有dp[i][j]==true时，才可能更新MaxLen和begin
                    if(dp[i][j] && MaxLen < j-i+1)
                    {
                        begin = i;
                        MaxLen = j-i+1;
                    }
                }
            }
            // cout<< begin<<"#"<<MaxLen;
            return s.substr(begin, MaxLen);
        }
    };

    // 220629 B站实习面试第一轮
    class Solution {
    public:
        string longestPalindrome(string s) 
        {
            int n = s.size();
            int maxlen = 1;
            int l=0;
            if(n <= 1) return s;
            vector<vector<bool>> dp(n, vector<bool>(n, false));
            for(int i=0; i<n; ++i)
            {
                dp[i][i] = true;
            }
            for(int i=n-1; i>=0; --i)
            {
                for(int j=i+1; j<n; ++j)
                {
                    int len = j-i+1;
                    if(len <=2) 
                    {
                        dp[i][j] = (s[i]==s[j]);
                    }
                    else if(len>2)
                    {
                        dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
                    }
                    if(dp[i][j] && len > maxlen)
                    {
                        maxlen = len;
                        l = i;
                    }
                }
            }
            string res = s.substr(l, maxlen);
            return res;
        }
    };

2. 正则表达式匹配

  • 题目描述：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.'（匹配任意单个字符） 和 '*'（匹配零个或多个前面的那一个元素） 的正则表达式匹配。所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串

    1
    2
    3
    4
    5
    6
    7
    输入：s = "ab", p = "abc*"
    输出：true
    解释：当"c*"匹配0个"c"时，p = "ab" = s 

    输入：s = "ab", p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

  • 解题思路：

    • dp[i][j]：表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配

    • 动态转移方程：

      1
      2
      3
      4
      5
      6
      7
      8
      if p[j] == s[i] : dp[i][j] = dp[i-1][j-1]
      if p[j] == '.' : dp[i][j] = dp[i-1][j-1]
      if p[j] == '*'：
      	if p[j-1] != s[i] : dp[i][j] = dp[i][j-2] // 此时相当于把p[j-1:j] = 'a*'整体抛弃
      	if p[j-1] == s[i] or p[i-1] == '.'： // 相当于p[j-1:j]和s[i]匹配了，因此只用考虑两者的前面是否匹配
      		dp[i][j] = dp[i-1][j] // 看s中a多不多，去掉一个是否还能匹配上 in this case, a* counts as multiple a
      		or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a	可以和上一个情况合并
      		or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty

    • 初始化：在 s 和 p 之前都添加一个 ' ' 字符，这样就可以避免 s='',p='a*' 这种情况

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution {
    public:
        bool isMatch(string s, string p) {
            s=" "+s;//防止该案例：""\n"c*"
            p=" "+p;
            int m=s.size(),n=p.size();
            bool dp[m+1][n+1];
            memset(dp,false,(m+1)*(n+1));
            dp[0][0]=true;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=n;j++){
                    if(s[i-1]==p[j-1] || p[j-1]=='.'){
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else if(p[j-1]=='*'){ // j=1时，不可能进入这个判断内部，因此p[j-2]不会越界
                        if(s[i-1]!=p[j-2] && p[j-2]!='.')
                            dp[i][j]=dp[i][j-2];
                        else{
                            dp[i][j]=dp[i][j-1] || dp[i][j-2] || dp[i-1][j];

                        }
                    }
                }
            }
            return dp[m][n];
        }
    };
欲戴皇冠，必承其重，加油！