《数据结构与算法之美》28——动态规划理论

2020-12-18 16:36

阅读:808

标签:文章   二层   推导   表示   不同   总结   说明   适合   tps   

前言

上一节通过两个经理案例初步认识动态规划,今天这一节主要讲动态规划的理论知识。

“一个模型三个特征”理论讲解

实际上,动态规划作为一个非常成熟的算法思想,这部分理论总结为“一个模型三个特征”。

一个模型

一个模型指动态规划适合解决的问题模型。这个模型定义为“多阶段决策最优解模型”。

一般是用动态规划来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的值。

三个特征

三个特征分别是:最优子结构无后效性重复子问题

  • 最优子结构:问题的最优解包含子问题的最优解。
  • 无后效性:有两层含义。
    1. 第一层,在推导后面阶段的状态时,只关心前面阶段的状态值。
    2. 第二层,某阶段的状态一旦确定,就不受之后阶段的决策影响。
  • 重复子问题:不同的决策序列,到达某个相同的阶段时,可能会产生重复的状态。

两种动态规划解题思路总结

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

状态转移表法

状态转移表法的解题思路概括为:回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码

我们来看一下,如何套用状态转移表法来解决动态规划问题。

假设我们有一个n乘以n的矩阵w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角,终止位置在右下角。那从左上角移动到右下角的最短路径长度是多少?

技术图片

回溯算法实现

public class Solution {
    private int minDist = int.MaxValue;
    public int MinDist { get { return minDist; } }
    // 调用方式:MinDistBT(0, 0, 0, w, n);
    public void MinDistBT (int i, int j, int dist, int[][] w, int n) {
        // 到达n-1, n-1这个位置了
        if (i == n - 1 && j == n - 1) {
            dist = dist + w[i][j];
            if (dist 

定义状态

从回溯代码的函数调用可知,每一个状态包含三个变量(i, j, dist),其中 i,j 分别表示行和列,dist 表示从起点到达(i, j)的路径长度。

画递归树

有了回溯代码和状态定义,把每个状态作为一个节点,画出递归树。

技术图片

找重复子问题

从上图可知,存在重复子问题。

画状态转移表

我们画出一个二维状态表,表中的行、列表示棋子所在的位置,表中的数值表示从起点到这个位置的最短路径。

根据递推关系填表

按照决策过程,通过不断状态递推演进,将状态表填好。

技术图片

将填表过程翻译成代码

public class Solution2 {
    public int MinDistDP (int[][] matrix, int n) {
        int[][] states = new int[n][];
        for (int i = 0; i 

状态转移方程法

状态转移方程法的解题思路概括为:找最优子结构-写状态转移方程-将状态转移方程翻译成代码

还是拿上面的例子来说明。

找最优子结构

min_dist(i, j)可以通过min_dist(i, j-1)和min_dist(i-1, j)两个状态推导出来,符合“最优子结构”。

写状态转移方程

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

强调一下,状态转移方程是解决动态规划的关键

将状态转移方程翻译成代码

一般情况下,有两种代码实现方法:

  • 递归+“备忘录”
  • 迭代递推

用递归+“备忘录”将状态转移方程翻译成代码。

public class Solution3 {
    private int[, ] matrix = new int[4, 4] { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 } };

    private int n = 4;
    private int[, ] mem = new int[4, 4];

    public int MinDist (int i, int j) { // 调用MinDist(n-1, n-1)
        if (i == 0 && j == 0) return matrix[0, 0];
        if (mem[i, j] > 0) return mem[i, j];
        int minLeft = int.MaxValue;
        if (j - 1 >= 0) {
            minLeft = MinDist (i, j - 1);
        }
        int minUp = int.MaxValue;
        if (i - 1 >= 0) {
            minUp = MinDist (i - 1, j);
        }

        int curMinDist = matrix[i, j] + Math.Min (minLeft, minUp);
        mem[i, j] = curMinDist;
        return curMinDist;
    }
}

总结

动态规划有两种解题思路:状态转移表法和状态转移方程法。

状态转移表法的解题思路概括为:回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码

状态转移方程法的解题思路概括为:找最优子结构-写状态转移方程-将状态转移方程翻译成代码

参考资料

  • 41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

《数据结构与算法之美》28——动态规划理论

标签:文章   二层   推导   表示   不同   总结   说明   适合   tps   

原文地址:https://www.cnblogs.com/liang24/p/13384809.html


评论


亲,登录后才可以留言!