本文主要对动态规划对应的例题和思路进行整理。动态规划常用于字符串匹配中,其探讨最优子状态。如何代表最优子状态,以及最优子状态之间的转移关系,就是动态规划的重点,所以在介绍思路的时候,也是就简介绍子状态是什么,如何转移。

动态规划

题1:Regular Expression Matching

思路:以$dp[i][j]$表示s字符串对应下标$i-1$和p字符串对应下标$j-1$的匹配关系。

二维数组的状态转移方程:$dp[i][j] = f(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])$,只不过在这个题中考虑的状态比较复杂和多一点而已。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        auto match = [&](int i, int j){
            if(i==0){
                return false;
            }
            if(s[i-1] == p[j-1]||(p[j-1] == '.')){
                return true;
            }
            return false;
        };
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        dp[0][0] = 1;
        for(int i = 0 ; i <= m; i++){
            for(int j = 1; j <= n; j ++){
                if(match(i,j)){
                    dp[i][j] |= dp[i-1][j-1];
                }
                if(p[j-1] == '*'){
                    // 前面的字符出现0次,即消除前一个字符
                    if(j>1){
                        dp[i][j] |= dp[i][j-2];
                    }
                    // 前面的字符出现多次,即*复制字符进行匹配,若s[i-1]是前面的扩展即可,就要看[i-1][j]的匹配情况,如果匹配好,就可以扩展。
                    if(match(i,j-1)){
                        dp[i][j] |= dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

题2:字符串匹配: Pattern Matching LCCI

这个做法,整个思路流程非常的通畅,从特殊情况简单处理,到复杂情况复杂处理。

class Solution {
public:
    int cnt[2];
    bool patternMatching(string pattern, string value) {
        // From simple to complex
        // consider one of the Strings equals to null.
        // merge all the possibilities to get a simpler form.
        // note the special
        if(pattern.empty()) return value.empty();
        if(value.empty()){
            int i = 0;
            while(i < pattern.size() && pattern[i] == pattern[0]) i++;
            return i == pattern.size();
        }
        int n = pattern.size(), m = value.size();
        cnt[0] = cnt[1] = 0;
        for(auto x: pattern) cnt[x-'a']++;
        // if(helper(value,cnt[0]) || helper(value, cnt[1])) return true;  
        // 上面这个代码如果统一的话,没有截止等于0的情况,后面取余数会有问题。
        if(!cnt[0]) return helper(value, cnt[1]);
        else if (!cnt[1]) return helper(value, cnt[0]);
        if (helper(value, cnt[1])) return true;
        if (helper(value, cnt[0])) return true;
        // In the following steps, a and b can not equals to null.
        for(int lena = 1; lena*cnt[0] <= m - cnt[1]; lena++){
            if((m-lena*cnt[0])%cnt[1] != 0) continue;
            int lenb = (m-lena*cnt[0])/cnt[1];
            if(check(pattern, value, lena, lenb)) return true;
        }
        return false;
    }
    bool helper(string value, int k){
        // 判断是否能切分k次,且全部相等。
        int m = value.size();
        if(m%k != 0) return false;
        int len = m/k;
        for(int i = len; i < m; i+=len){
            if(value.substr(i,len) != value.substr(0,len)) return false;
        }
        return true;
    }
    bool check(string pattern, string value, int lena, int lenb){
        string ps[2] = {"",""}; // double quotations
        // c++好像字符串不能直接相等。
        // j是该模式起始的位置。
        for(int i = 0, j = 0; i < pattern.size(); i++){
            if(pattern[i] == 'a'){
                // 如果没有被赋值,首先赋值,之后再进行比较。
                if(ps[0] == "") ps[0] = value.substr(j, lena);
                else if (value.substr(j,lena) != ps[0]) return false;
                j += lena;
            }
            else{
                if(ps[1] == "") ps[1] = value.substr(j, lenb);
                else if (value.substr(j, lenb) != ps[1]) return false;
                j += lenb;
            }
        }
        return true;
    }
};

题3:动态规划/递归转换:Unique Binary Search Trees II

思路:递归比较容易,只需要考虑主问题和次问题之间是怎么连接的,从上到下考虑即可。动态规划需要从下到上,看最优的子状态是如何形成最终的状态的,注重于状态之间的转换关系。一般情况下两者都是可以转换的。只要建立好子结构就可以。

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        # recursion,main section -> smaller section with same function.
        # dynamic pogramming -> relations between consecutive states, several states -> one state.
        # This is a binary search tree.
        # method 1, recursion.
        def helper(s, e):
            # e is exclusive, s is inclusive 
            # return all the possibilities under the root
            res = []
            if s >= e:
                return [None]
            for i in range(s,e):
                left = helper(s, i)
                right = helper(i+1, e)
                for l in left:
                    for r in right:
                        temp = TreeNode(i)
                        temp.left = l 
                        temp.right = r
                        res.append(temp) 
            return res 
        if n == 0:
            return None
        return helper(1,n+1)

题4:Counting Bits

思路:在动态规划中,可以分类建立子状态的关系,这道题就是把奇数和偶数分开,奇数和偶数之间的差别,奇数之间差1,偶数之间差1,建立联系即可。

所以关键就是这里并非是连续的状态转换关系,而是差了个2.

class Solution:
    def countBits(self, num: int) -> List[int]:
        # 1,10,11,100,101....
        dp = [0 for i in range(num+1)]
        dp[0] = 0
        # 找到奇偶之间的关系,奇数比之前的偶数+1,偶数比之前的num>>1的数一样的。
        # 关系可以是分开创建的,即奇数和奇数建立联系,偶数和偶数建立联系。
        for i in range(1,num+1):
            if i%2 == 0:
                dp[i] = dp[i>>1]
            else:
                dp[i] = dp[i>>1] + 1
        return dp

题5:Stone Game

思路:是在二维 dp 的基础上使用元组分别存储两个人的博弈结果。动态规划的思路,其实本质上就是强化学习的思路,就是属于当前状态+选择过程。

tips:一般情况下,动态规划都可以写成递归,所以可以先用递归的方式想问题,找到状态之间的转移关系。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        # 如果每次每个人都做出最优的选择,Alex还是赢,说明Alex must win the game
        # 因此在该问题中,每个人的策略都是相同的,可以用一个dp数组表示。
        n = len(piles)
        dp = [[piles[i] if i == j else 0 for i in range(n)] for j in range(n)]
        # 根据状态转移关系,为了满足从最小子状态建立的流程,需要从base的情况考虑dp数组如何遍历。
        # 在下面的遍历中,i表示包含的元素个数-1,j表示起始位置,dp[s][e]中s,e表示开始的位置和最后的位置。
        for i in range(1,n):
            for j in range(n-i):
                dp[j][j+i] = max(piles[j] - dp[j+1][j+i], piles[j+i] - dp[j][j+i-1])
        return dp[0][n-1] > 0                

题6:Longest Valid Parentheses

思路:dp[i]表示以当前字符为结束的有效字符串长度(注意不是有效括号个数)。

其中这个问题有个隐藏的约束:即有效字符串的内部必须全部都是有效的括号,不可以单单出来一个字符。

总结:

还有一类问题,状态设置是以当前字符或者当前下标作为边界的状态,在这里是有效字符串的长度。

差别就是一个必须包含最后的字符作为结束字符,一个不需要包含最后的字符。

上面两种不同的状态设置方式,主要有两个差别:

  • 最后做O(n)的max(dp)的运算,或者直接输出dp[-1]

  • 以当前index作为边界的状态设置少了一个必须包含当前元素的约束,需要考虑多种情况.

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 有效括号字符串,内部必须全部都是有效括号字符串.
        dp = [0 for i in range(len(s))]
        res = 0
        for i in range(1,len(s)):
            if s[i] == ')':
                pre = i - dp[i-1] - 1
                if pre >= 0 and s[pre] == '(':
                    dp[i] = dp[i-1] + 2
                    if pre > 0:
                        dp[i] += dp[pre-1]
            res = max(res,dp[i])
        return res 

题7:Count Numbers with Unique Digits

思路:这里的状态选择的位数,即dp[i]代表i位数的所有情况。

有了状态的选择之后,就可以状态之间的转移方程:dp[i] = dp[i-1] + (dp[i-1]-dp[i-2])*(10-(i-1))

其中,dp[i-1]-dp[i-2]是只考虑位数为i-1的情况,然后和最后一位的个数相乘,是一种排列组合。

由于i只依赖于i-1i-2,所以这里可以采用节省内存的dp。

NOTE: 第一位为0不贡献位数,仍然是i-1

Summary:

动态规划其实就两个步骤:

  • 状态的选择,dp[i]代表什么,dp[i][j]...代表什么状态,要有代表性,可以设置多个状态数组。
  • 状态的转移,不同状态之间的关系是什么,或者不同状态数组之间的转移是什么
class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        if n == 1:
            return 10
        a = 1
        b = 10
        # b - a 是一种推导结果,只考虑i-1位的情况,最后一位的情况要看现在总共有多少位数。
        # 0不贡献位数。
        for i in range(2,n+1):
            c = b + (b-a)*(10-(i-1))
            a = b
            b = c
        return c

题8:Wildcard Matching

summary:动态规划的状态延续性,在某种程度上是一种承接,后一个状态可以由前一个状态修改后获得,也可以承接前一个状态,在这道题中,承接性做的好,省去了很多麻烦。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # classic dynamic programming
        # is it possible to have consecutive symbol "**"??
        m = len(s)
        n = len(p)
        dp = [[False for i in range(n+1)] for j in range(m+1)]
        dp[0][0] = True
        
        for j in range(1,n+1):
            if p[j-1] == "*":
                dp[0][j] = dp[0][j-1]
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if (s[i-1] == p[j-1]) or p[j-1] == "?":
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    dp[i][j] = dp[i-1][j] or dp[i][j-1] # empty sequence
    
        return dp[-1][-1]

动态规划+二分

题1:354. 俄罗斯套娃信封问题

题2:673. 最长递增子序列的个数

题3:646. Maximum Length of Pair Chain

未分类

LCP 19. 秋叶收藏集

思路:动态规划还是最重要的两个问题:

  • 状态的表示,用什么来表示一个状态,dp[i][j]表示什么意思?
  • 状态的转移关系,是如何利用子状态建立起来当前状态的?

在这个题中,dp[i][j]可以表示为当前的位置为i处于j状态时的最小个数,j可以分为三个状态,即前面的红,后面的红,中间的黄,是按照顺序划分的,并不是按照种类划分的。

Binary Tree Cameras

思路:当一个节点的状态与父节点和子节点(在数组中就是前面的状态和后面的状态会同时作用于当前的状态),该节点的状态一般有三个,其一是选择1,其二是被子节点的1影响,其三是被父节点的1影响,子节点没有作用。

贪心/动态规划:514. Freedom Trail

思路:一开始认为应该用贪心来解,但是贪心有本质上的缺点,它和动态规划的区别在于,贪心如果是正确的解,那么它每一步的解应该都能证明是最优解。如果是动态规划的话,前面的解不一定是最优解,我可以用数组来存储当前状态下的解,一步步递进求出全局最优解。

动态规划+位运算:338. Counting Bits

思路:动态规划,重要的是状态表示和转移关系,在转移关系中,除了+1,-1,+2,-2等,还有关于index的位运算,即num[i»1]和num的关系如何。