浅谈动态规划

编程算法

字数统计: 1.6k阅读时长: 6 min

 2020/04/05   Share

概念

动态规划（Dynamic programming，简称 DP），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。这与递归的思想一致，所以动态规划往往用于优化递归问题，利用动态规划的思想可以减少计算量。

最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。即我们可以通过子问题的最优解，推导出问题的最优解。

无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。

重复子问题

不同的决策序列，到达某个相同阶段时，会产生重复的状态。

实践

思路总结

解决动态规划问题，一般有两种思路，分别为状态转移表法和状态转移方程法。

状态转移表法

一般情况下，能使用动态规划解决的问题，都可以使用回溯法解决。先通过回溯法，找到是否存在重复子问题，以及相应的规律，尝试是否能使用动态规划解决。
找到重复子问题之后，就可以使用状态转移表来处理问题。
先画出一个状态表，一般来说都是二维的，可以用二维数组来表示，其中每个状态包括三个变量，行，列，数组值。根据递归关系，填充状态表的每个状态，最后翻译成代码，就是动态规划的代码了。
但如果问题较为复杂，状态表就有可能是高维的，这时候人在思考问题的时候就不那么简单了。
举个例子，要从矩阵左上角走到矩阵右下角，但是每格都有相应的权重，我们需要选择权重最小的路径。
这里我们可以采用回溯算法(深度优先中的一种)，回溯在遍历时不保留完整的结构，而深度优先则保留。

class Solution:
    self.minDist = float('inf')
    def minDistBT(i:int,j:int,dist:int,w:list[list[int],n:int):
        if i == n and j == n:
            if dist < minDist:
                self.minDist = dist
            return
        if i < n:
            self.minDistBT(i + 1,j,dist + w[i][j] , w, n)
        if j < n:
            self.minDistBT(i,j + 1,dist + w[i][j] , w, n)

我们可以看出，一个状态即一个节点，包含三个变量(i,j,dist)，其中i,j表示行列，dist表示起点到(i,j)的路径长度，尽管(i,j,dist)没有重复值，但(i,j)重复，对于(i,j)重复的节点，我们只需要选择dist最小的节点便可以继续递归求解了。
我们翻译成代码：

class Solution:
    def minDistDP(matrix:list[list[int]],n:int):
        states = [[0 for _ in range(n)] for _ in range(n)]
        sum = 0
        for i in range(n):
            sum += matrix[0][i]
            states[0][i] = sum
        
        sum = 0
        for i in range(n):
            sum += matrix[i][0]
            states[i][0] = sum
        
        for i in range(1,n):
            for j in range(1,n):
                states[i][j] = matrix[i][j] + min(states[i][j-1],states[i-1][j])
        return states[n-1][n-1]

这里我们初始化了第一行和第一列的数据，然后每一个节点都是让该节点的权重加上，上方和左方中的最小值，就是该状态表的这个节点的最小dist值。最后返回右下角节点的值，便可以获得最短路径。

状态转移方程法

这种方法与递归的思想类似，我们需要知道，某个问题如何通过子问题求解，即寻找最优子结构，根据最优子结构写出递归公式，即状态转移方程。以上面的问题来说，状态转移方程为：
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
状态转移方程是解决动态规划的关键所在，接下来翻译成代码

class Solution:
    self.matrix = [[random.randint(1,10) for _ in range(4)] for _ in range(4)]
    self.n = 4
    self.mem = [[0 for _ in range(4)] for _ in range(4)]
    # 调用minDist(n-1,n-1)
    def minDist(i:int,j:int):
        if i == 0 and j == 0:
            return self.matrix[0][0]
        if self.mem[i][j] > 0:
            return self.mem[i][j]
        
        minLetf = float('inf')
        if j - 1 >= 0:
            minLetf = self.minDist(i,j-1)
        minUp = float('inf')
        if i - 1 >= 0:
            minUp = self.minDist(i-1,j)

        currMinDist = self.matrix[i][j] + min(minLetf,minUp)
        self.mem[i][j] = currMinDist
        return currMinDist

我们从右下角回溯到左上角。每个节点的值等于该节点的权重加上上方和左方节点中的最小值。
其实和上面的状态转移表法的实现是差不多的，只是思考的思路不同。

总结

尽管动态规划比回溯算法高效，但并不是所有问题都可以使用动态规划，能使用动态规划的问题，需要满足三个条件，最优子结构，无后效性，重复子问题。在重复子问题上，动态规划与分治算法区分明显，分治算法要求分割成的子问题不能有重复子问题，而动态规划则恰恰相反，它之所以高效，是因为回溯算法中存在大量的重复子问题。
解决动态规划问题的思路分别是状态转移表法和状态转移方程法。其中，状态转移表法解题思路大致可以概括为回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。状态转移方程法的大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。
之后的文章会通过实际问题继续探讨动态规划。

原文作者：Zer0e

原文链接：https://re0.top/2020/04/05/dp1/

发表日期：四月 5日 2020, 4:10:00 下午

更新日期：April 7th 2020, 3:23:13 pm

Next Post

几种二分查找的模板与理解
Previous Post

二叉树的广度优先(层次)遍历

CATALOG

1. 概念
2. 实践
1. 2.1. 思路总结
  1. 2.1.1. 状态转移表法
  2. 2.1.2. 状态转移方程法
3. 总结

