贪婪和动态规划

贪婪算法和动态规划算法都是在多阶段决策最优解模型下求最优解。使用这两种算法可以算出来的，当然就可以使用brute-force的方式计算出来，但是关键的是，brute-force的计算一般是指数级的，比贪婪和动态规划大一个数量级，这就是一个比较致命的地方。

对于贪婪和动态规划，这两种算法是属于组合数学中的内容，贪婪算法还比较形象，对于动态规划这个名字，就优点摸不着头脑，最简单的叫法应该叫递推算法，后一次基于前一次来计算。一个有趣的历史是，当年发明这个算法的科学家为了向美国军方申请经费，他知道军方不喜欢数学，因此用了一个比较中性的名字dynamic programming来申请经费。实际上就是递推算法，感兴趣的同学可以到《离散数学》的书讲动态规划一节的批注中去阅读这个有趣的事情。

这两个算法不同于回溯和分治，没有什么具体的模版，唯有明白原理后多练习。

贪婪算法

贪婪算法比较好理解，就是每一步都选取当前最好的，得到的结果就会是相对最优，但是不能保证是最优。
下面选取leetcode上的122题

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

使用贪婪算法，如果后一天比前一天高，就将股票买卖，代码如下：

    def maxProfit(self, prices: list[int]) -> int:
        result = 0
        if len(prices) == 0:
            return 0
        prev = prices[0]
        for p in prices[1:]:
            if p > prev:
                result += p - prev
            prev = p
        return result

时间复杂度是O(n)

动态规划

下面我们用一道leetcode上比较经典的题目44题来学习来学习训练一下贪婪和动态规划算法。题目如下：

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

题目就是实现正则表达式，其中有两个通配符"?"和""， 其中""代表0个或者任意多个字符，而"?"代表任意一个字符，并且约束字符的大小是a-z。注意这和java的“*”表达不太一样，java的表达的是匹配0个或者多个其前面的字符。

brute-force

为了对比，当然首先暴力求解，代码如下：

    def isMatch_recursive(self, s: str, p: str) -> bool:
        if not p: return not s 
        if p[0] == '*' :
            return True if len(p) == 1 else (self.isMatch(s, p[1:]) or (s and self.isMatch(s[1:], p)))
        else:
            return s and (self.isMatch(s[1:], p[1:]) if s[0] == p[0] or p[0] == '?' else False)

这里比较难思考的是“”的语义表达，“”就是说匹配0个或者匹配多个，表达就是

(self.isMatch(s, p[1:]) or (s and self.isMatch(s[1:], p)))

另外对于边界条件s是否不为空，以及单独一个"*"可以匹配任何字符串，这样的要考虑正确。

算法巧妙，但是要分析时间复杂度，通过递归树分析，时间复杂度O(2^len(s) * 2^len(p))，就是一个指数级的复杂度。但是实际运行时由于边界的存在，不会有那么高。

动态规划

即递归求解，动态规划有两种求解方法：

• 状态转移表
• 状态转移方程
  状态转移方程就是其中的关键，对于这个题，我们采用状态转移表来实现，状态转移方程为：

    # P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
    # P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.v

就是说做一个(len(s)+1) * (len(p)+1)，其中表的第一列代表p为空，第一行代表s为空。将该表初始化为值权威False的表，并且将(0,0)这个点赋值为True，当s和p都为空的时候，是匹配的。下面我们用一个例子推导一下：

• 初始态

  
  image.png

• p的第一个字符"*"
  此时用上上述递推公式

  
  image.png

• p的第二个字符"b"

  
  image.png

-p的第三个字符c

image.png

最后返回最右边的值
代码如下：

    def isMatch(self, s: str, p: str) -> bool:        
        r = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        r[0][0] = True
        print(r)
        for j in range(1, len(p)+1):
            if p[j-1] == '*':
                for i in range(len(s)+1):
                    r[i][j] = r[i][j-1] if not i else (r[i-1][j] or r[i][j-1])
            else:
                for i in range(1, len(s) + 1):
                    r[i][j] = r[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '?')
            print(r)
        return r[len(s)][len(p)]

计算时间复杂度O(len(s) * len(p))，这就是一个常数级别的，比暴力算法复杂度低非常多。

小结

贪婪和动态规划算法非常考验人的智力，特别是动态规划，这类题目在google的面试题占比达到20%多，所以有什么理由不学好呢。