Python - 深夜数据结构与算法之 DP

一.引言

常规算法介绍的差不多，最不喜欢的动态规划 Dynamic Programming 还是来啦，前面介绍贪心算法时以及一些最大最小收益等等的问题，其实都可以套用动态规划的思路来实现的，下面我们看看动态规划的思路与模版要点。

二.动态规划的简介

1.递归 Recur?

分治、递归、回溯以及本节的动态规划都有相似之处，介绍动态规划前我们再继续回顾下前面的数据结构以及模版，这些都要做到不断地重复不断地重复，有相关的问题直接模版就能够出来，再修改细节。?

- terminator 终止条件

- process 当前层处理逻辑

- drill down 到下一层继续处理

- restore 需要回复一些状态变量

2.分治 Divide Conquer

同理，分治也有其模版套路，主要是 Split Sub Problem 以及 Merget Sub Problem。同样有其对应的终止条件，一般是子问题无法再向下细分时的最小问题，最终将多个 sub result 进行合并得到全局的 result。

- terminator 终止条件

- split 大问题拆分为小问题

- conquer 分别递归将小问题继续拆分

- merge 合并多个 sub_result 结果

3.动态规划 DP

动态规划 DP 也是在一定分治的基础上寻找最优子结构的过程。中间这句英语的意思是 '将一个复杂的问题分解成一个简单的子问题'，这个也印证了前面说的分治。而最优子结构则是 DP 算法一般用于求解最优路线、最短路线、最值等等，其需要存储一个最优的状态并不断更新。

这里本质上其实和递归分治没有太大区别，核心都是找到问题的重复性并不断尝试，同时最优子结构可以做到在比较中淘汰不好的留下更好的。?

3.经典算法实战

1.Fib [509]

斐波那契数列:?https://leetcode.cn/problems/fibonacci-number/description/

◆ 题目分析

典中典的题目，分治回溯的鼻祖，这里我们别使用之前的方法和基于 DP 的方法进行解答，正所谓经不经典我不管，我只需要这一款啊。

◆ 双指针实现

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        a, b = 0, 1

        # 向右移动
        for i in range(n):
            a , b = b, a+b
        
        return a

前面介绍过很多次了，这里不再赘述，下面看下 DP 的思路。?

◆ DP 实现

class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        cache = {0:0, 1:1}
        
        return self.fib_by_dp(n, cache)

    def fib_by_dp(self, n, cache):
        if n not in cache:
            cache[n] = self.fib_by_dp(n-1, cache) + self.fib_by_dp(n-2, cache)
        return cache[n]

DP 就是在实现过程中存储状态变量并更新至最优，我们这里最优其实就是到达最终目标值即可。

上面的图可以看到，直接 f(n-1) + f(n-2) 计算时，随着 level 的增加，需要计算的问题呈指数级展开，采用缓存后，问题得到剪枝，只需要 o(n) 的时间复杂度即可。

不过这个方法由于加入了 cache 的 dict，所以空间复杂度相较之前的方案有一定增加，但执行速度上大同小异。?第一种方法其实是一种自下而上的思维，而下面的方法则是自上而下，在过程中添加缓存。我们的人脑一般多是下面这种思维结构，拿到问题 f(n) 然后 f(n-1) 这样，以后遇到问题也可以想想自下而上的思路是否可行。

2.Unique-Paths [62]

不同路径:?https://leetcode.cn/problems/unique-paths

◆ 题目分析

对于第一行和第一列的所有位置，机器人只有1种走法可以到达，一路向南和一路向东，所以这两路都标注为 1，其余每个位置的走法都等于其上面和左边走法之和，对于 (1,1) 这个点，可以 (1,0) -> (1,1) 也可以 (0, 1) -> (1,1)，所以其走法等于二者之和，其余的点同理。

◆ DP 实现?

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        # m 行 n 列的矩阵
        mat = [[1] * n]
        for i in range(m-1):
            mat.append([1] + [0] * (n-1))
    
        # 进行累加
        for i in range(1, m):
            for j in range(1, n):
                mat[i][j] = mat[i-1][j] + mat[i][j-1]
    
        return mat[m-1][n-1]

按照上面的思路，初始化行和列的 1 后，向左右累加即可。?

◆ DP 实现 - 内存优化?

class Solution:
    def uniquePaths(self, m, n):
        # m 行 n 列的矩阵
        cur, next = [1] * n, [1] * n

        # 进行累加
        for i in range(1, m):
            for j in range(1, n):
                next[j] = cur[j] + next[j - 1]
            cur = next[:]

        return next[-1]

上面我们 for i in range(n) 遍历行，起始有上下两行的内存即可，相当于双指针不断向下走即可。运行速度和上面一致，但是内存节省了很多。上面提到了自上而下和自下而上，对于本题这个思想也适用，机器人从左上角到右下角终点有多少种走法，右下角终点到机器人所在起点就有多少种回去的方法，有兴趣的同学也可以反过来实现一遍，体会这两种思维方式。

◆ 排列组合

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        re = 1
        st = m + n - 2
        down = 1
        for i in range(1, n):
            re *= st
            st -= 1
            down *= i

        return re // down

这个题还有一个思路就是使用排列组合，对于一个 mxn 的网格，机器人想要到达终点一点要向下 n-1 步，向右 m - 1 步，所以可以看作是组合问题，M+N-2 个格子，n-1 个放 👇🏻，m-1 个位置放 👉🏻，直接套用组合公式即可。

3.Unique-Paths 2 [63]

不同路径2:?https://leetcode.cn/problems/unique-paths-ii/

?◆ 题目分析

与上题目标一致，是机器人从 A 点到 B 点，区别是这次添加了障碍物，当遇到障碍物时，此路为死路，此时路径的可能性就不是其上面和左面的和了，而是 0。

◆ 动态规划

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):

        n = len(obstacleGrid)
        m = len(obstacleGrid[0])

        dp = [0] * m
        #起点可能有障碍物
        dp[0] = 1 if obstacleGrid[0][0] == 0 else 0

        for i in range(n):
            for j in range(m):
                #有障碍物的格子直接赋0
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                #否则dp[j]的值由左方和上一次迭代的dp[j]累加而来    
                elif obstacleGrid[i][j] == 0 and j - 1 >= 0:
                    dp[j] = dp[j] + dp[j - 1]
                    
        return dp[-1]

?对于 [i][j] == 1 的障碍物格子，其值为 0 不会有走法走到这里。

◆ 递归实现

class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):

        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        d = {}
        def dfs(i, j):
            if (i,j) in d:
                return d[i,j]
            #边界/障碍物检查    
            if i >= m or j >= n or obstacleGrid[i][j] == 1:
                return 0		
            #达到重点了    
            if i == m - 1 and j == n - 1:
                return 1
            #继续往右(i,j+1)、往下(i+1,j)递归调用    
            d[i,j] = dfs(i + 1, j) + dfs(i, j + 1)
            return d[i,j]
        return dfs(0, 0)

这个思路就是自底向上的，终点不会有障碍物，其值为 1，我们一步一步加回去即可。每个题都没有固定的解法，还是不能养成惯性思维。

4.LCS [1143]

最长公共子序列:?https://leetcode.cn/problems/longest-common-subsequence?

◆ 题目分析

最长公共子序列是典型的动态规划问题，对于字符串 s 和 t 而言，其有两种情况，如果两个索引位置的字符相同，子序列公共部门 +1，然后计算 s[i-1] 和 t[j-1] 的最长公共子串即可，如果二者不相等，则最长公共子串需要判断两个方向，要么 s[i-1] 和 t[j] 或者 s[i] 和 t[j-1]:

?◆ 动态规划

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        m, n = len(text1), len(text2)

        # 构建 m+1 x n+1 的网格
        dp = [[0] * (n+1) for _ in range(m+1)]

        # 从 (1,1) 开始，防止越界
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i - 1] == text2[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[m][n]

下图展示了如何通过状态转移计算 s 与 t 的最长公共子串长度。 当我们遇到子序列类型的问题，穷举出所有可能的结果都不容易，而动态规划算法做的就是穷举 + 剪枝，它俩天生一对儿。所以可以说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。

?◆ 暴力解法

class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
    
        m, n = len(text1), len(text2)

        def dfs(i, j):

            # str = "" 的 bad case
            if i == -1 or j == -1:
                return 0
        
            if text1[i] == text2[j]:
                # 一样就都截取一个字符
                return dfs(i - 1, j - 1) + 1
            else:
                # 取更大的可能
                return max(dfs(i - 1, j), dfs(i, j - 1))
        
        return dfs(m - 1, n - 1)

这个思路其实就是最原始的解法，但是遍历的情况很多会导致运行超时，所以才有了上面我们使用 DP Table 进行缓存的方法，这里动态规划要学会使用缓存结果，构建 i/j 之间的转换关系:

5.Triangle [120]

三角形最小路径和:?https://leetcode-cn.com/problems/triangle/description/

◆ 题目分析

根据最下层的 m 个数，可以遍历更新上一层 m-1 个数里的最小值，持续向上更新即可。

◆ 自下而上 DP

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """

        " re = min([row, j], [row, j+1]) "

        dp = triangle

        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                # 每一个位置，都更新为其最小值
                dp[i][j] += min(dp[i+1][j], dp[i+1][j+1])
        
        return dp[0][0]

◆ 自上而下 DFS?

class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """

        " re = min([row, j], [row, j+1]) "
        # 
        row = len(triangle)
        cache = {}

        def dfs(level, col, triangle):
            # 有缓存直接返回
            if ((level, col) in cache):
                return cache[(level, col)]
            
            # 到达最后一层了
            if (level == row - 1):
                return triangle[level][col]
            
            # 获取分叉的两个值
            left = dfs(level + 1, col, triangle)
            right = dfs(level + 1, col + 1, triangle)
            
            # 增加 Cache
            cache[(level, col)] = min(left, right) + triangle[level][col]
            return cache[(level, col)]
        
        return dfs(0, 0, triangle)

在暴力 DFS 的基础上，增加了 Cache 存储，不过效率一般，思路其实也是从下而上求最小，但是 DFS 是先自顶而下，再从下逐渐返回结果。

四.总结

动态规划的题目主要涉及到最优、 子问题等不方便穷举出所有可能的结果的问题。说只要涉及子序列问题，十有八九都需要动态规划来解决，往这方面考虑就对了。注意在 DFS 的过程中适当添加缓存，即空间换时间或者采用剪枝策略，因为 DP 在不优化的情况下，复杂度往往是指数级。