前言

做了些题，看了些大佬们的文章
现在对算法有那么点感觉
尝试总结归纳

本篇是动态规划详解（一）
从入门到熟练
通过一些例子讲明白动态规划是怎么一回事儿

1、什么是动态规划

动态规划这个名字不够接地气
说白了就是穷举
满足一些条件的穷举：

• 问题一般是求最值
• 存在重叠子问题
• 具备最优子结构

如是，我们就可以用个备忘录（dp）优化，进行迭代求解
这就是动态规划

具体求解过程：

• 确定状态
• 明确dp含义
• 正确的状态转移方程

动态规划说白了就是这么一回事儿
关键点就在于明确dp含义和给出状态转移方程
不同的状态转移方程，性能能差十万八千里

下面我们通过一些例子感受和学习动态规划是怎么一回事儿

2、斐波那契数列

我们从最简单的例子开始
斐波那契数列

• 这是个求最值的问题
• 也是具备重叠子问题
• 严格来说不算动态规划（没有最优子结构）

我们通过这个例子可以一窥思想

通常我们用的是暴力递归计算

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1: return N
        return self.fib(N - 1) + self.fib(N - 2)

看起来很好理解，但是计算量爆炸
其时间复杂度是O(2^n)
在leet上耗时800ms左右

那我们观察发现
（这里借用labuladong的图）

重复的计算是没有必要的
拿个备忘录记录下前两个的状态
就能减掉绝大多数重复计算
将这个树图变为自顶向下的线性图

在这里

• dp的意义就是前两个状态的值
• 状态转移方程自然是f(n)=f(n-1)+f(n-2)

于是我们可以写出解

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1: return N
        dp = [0, 1]
        for i in range(N-1):
            tmp = sum(dp)
            dp[0] = dp[1]
            dp[1] = tmp
        return dp[1]    

现在时间复杂度是O(n)
在leet上耗时40ms左右

3、零钱兑换

我们再来看个标准动态规划问题
leet上322题零钱兑换

给你 k 种⾯值的硬币，⾯值分别为 c1, c2 ... ck ，每种硬币的数量⽆限，
再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个⾦额，
如果不可能凑出，算法返回 -1

先来看这个问题

• 这是个求最值：最少几枚硬币
• 有重叠子问题：不同的amount，最少需要⼏枚硬币
• 有最优子结构：⼦问题间互相独⽴

那就要来进行动态规划思考

• 状态：目标金额amount
• dp含义：到达amount=n时最少需要dp(n)个硬币
• 状态转移方程：dp[i] = min(dp[i - coins[j]]) + 1，j遍历所有硬币

如是
我们就可以写出解了

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 自底向上
        # dp[i] 表示金额为i需要最少的硬币
        # dp[i] = min(dp[i - coins[j]]) + 1 j遍历所有硬币
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            dp[i] = min(dp[i - c] if i - c >= 0 else float("inf") for c in coins) + 1
        return dp[-1] if dp[-1] != float("inf") else -1

leet上耗时1260ms左右

4、最长上升子序列

leet上300题最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
例子
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

注意子序列不连续

同样进行分析：

• 求最值：题目说明一切
• 重叠子问题：截取一个子串也是同样的问题
• 最优子结构：子问题相互独立

那就可以进行动态规划了

• 状态：最长上升子序列的长度
• dp：前n个数中最长上升子序列的长度
• 状态转移方程：dp[i] = max(dp[i], dp[j] + 1)， j < i

于是我们可以写出解

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp or [0])

时间复杂度O(n^2)
leet耗时1280ms左右

注：leet上进阶要求将算法的时间复杂度降低到 O(n log n)
用的是二分

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        import bisect
        arr = []
        for num in nums:
            loc = bisect.bisect_left(arr, num)
            arr[loc:loc + 1] = [num]
        return len(arr)

5、正则表达式匹配

leet上10题正则表达式匹配

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

说明:
	s 可能为空，且只包含从 a-z 的小写字母。
	p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *

首先我们考虑一个简单的递归
捋清思路

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s  # 结束条件
        first_match = (len(s) > 0) and p[0] in {s[0], '.'}
        # 先处理 `*`
        if len(p) >= 2 and p[1] == '*':
            # 匹配 0个 | 多个
            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))
        # 处理 `.` ，匹配一个
        return first_match and self.isMatch(s[1:], p[1:])

当然这个效率极差，O(2^n)
leet耗时1380ms左右

然后我们考虑动态规划

• 状态：字符匹配
• dp：dp[i][j] 代表字符串 s 中前 i 个字符和 p 中前 j 个字符是否匹配
• 状态转移： p[n]为 ′∗′ 时： p[n−1]为 ′.′ 或 s[m]==p[n−1]，则dp[i][j]=dp[i−1][j]；否则dp[i][j]=dp[i][j−2]。当 p[n] 为 ′.′ 或 s[m]==p[n] 时： dp[i][j]=dp[i−1][j−1]

初始状态：

• 初始化第一行：dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'；
• Tips: p 第 j 个字符记为 ′∗′ 且 dp[0][j−2] 为 True

# dp
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        ls, lp = len(s), len(p)
        dp = [[False for _ in range(lp + 1)] for _ in range(ls + 1)]
        dp[0][0] = True
        for j in range(2, lp + 1):
            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
        for i in range(1, ls + 1):
            for j in range(1, lp + 1):
                m, n = i - 1, j - 1
                if p[n] == '*':
                    if s[m] == p[n - 1] or p[n - 1] == '.':
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j]
                    else: dp[i][j] = dp[i][j - 2]
                elif s[m] == p[n] or p[n] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[-1][-1]

时间复杂度O(MN)
leet耗时50ms左右

注：python好就好在库函数

# 库函数
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        import re
        a=re.compile(p)
        x=a.findall(s)
        if x and len(x[0]) == len(s):
            return True
        else:
            return False

leet耗时90ms左右

结语

通过以上几个例子
多少能学习到动态规划是怎么一回事儿
之后会归纳几个经典的动态规划问题