动态规划算法

一、基本定义

1.1、百度百科定义

动态规划是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

1.2、热度推荐定义一

动态规划（Dynamic Programming）在数学上属于运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法，同时也是计算机科学与技术领域中一种常见的算法思想。

1.3、热度推荐定义二

动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

1.4、个人理解

动态规划属于运筹学的范畴，是解决多阶段决策过程最优化的一种数学方法。它的理论并不高深，最有挑战的是能够把实际案例和理论关联起来，并且解决实际问题的能力。

二、适用场景

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

动态规划有三个特征约束：最优子结构、无后效性、重复子问题。

2.1、最优子结构

最优子结构指的是问题的最优解包含子问题的最优解。也可以说，通过子问题的最优解，可以推导出原问题的最优解。如果把最优子结构，对应到定义的动态规划问题模型上，那也可以理解为，后面阶段的状态可以通过前面的状态推导出来。

2.2、无后效性

在推导后阶段状态时，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。
某个阶段状态一旦确定，就不再受之后阶段的决策影响。

2.3、重复子问题

不同的决策序列，在到达某个相同的阶段时，可能会产生重复的状态。如果不使用动态规划，会导致重复问题的求解浪费过多时间，这也是回溯算法时间复杂度比较高的原因。

理论上能够用动态规则解决的问题，都可以用回溯算法和备忘录的形式，达到相同的效果。

2.4、解题思路

动态规则解题的思路基本就是两种：状态转移表法和状态转移方程法。

状态转移表法：状态表一般都是二维，你可以就把它想象成一个二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了。
状态转移方程法：状态转移方程法有点类似于递归的解题思路。基于某个子问题来递归求解，就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。状态转移方程是解决动态规划的关键，如果我们写出状态转移方程，那动态规划问题基本上就解决一大半了。

三、经典案例

掘金社区中介绍动态规划最热门的一些文章如下，它们的原理和解题的思路，和以上陈述的基本大同小异。

一文搞懂动态规划
 看一遍就理解：动态规划详解
 告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文）
动态规划套路
 关于硬币的几个动态规划问题
 一份给算法新人们的「动态规划」讲解

3.1、案例

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

3.2、回溯 + 备忘录

private int longest;
private int[][] mem2;
public int longestCommonSubsequence(String text1, String text2) {
    this.longest = 0;
    this.mem2 = new int[text1.length()][text2.length()];
    for (int i = 0; i < text1.length(); i++) {
        for (int j = 0; j < text2.length(); j++) {
            this.mem2[i][j] = -1;
        }
    }
    longest(0, 0, 0, text1, text2);
    return this.longest;
}

private void longest(int i, int j, int dist, String text1, String text2) {
    if (i >= text1.length() || j >= text2.length()) {
        this.longest = Integer.max(this.longest, dist);
        return;
    }

    // 使用备忘录解决重复子问题，只需要记录最大的匹配长度即可，小于等于时不需要再遍历
    if (this.mem2[i][j] >= dist) { 
        return ;
    }
    this.mem2[i][j] = dist;

    if (text1.charAt(i) == text2.charAt(j)) { // 字符相同，下标都往后移动一位，长度+1
        longest(i + 1, j + 1, dist + 1, text1, text2);
    } else { // 不相同，text1向后移动一位，或者text2向后移动一位
        longest(i + 1, j, dist, text1, text2);
        longest(i, j + 1, dist, text1, text2);
    }
}

3.3、动态规划

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return lwst(text1,text2);
    }
    public int lwst(String a, String b) {
        //表示遍历到a的第i个下标，b的第j个下标时，最大的公共子串 state[i][j]
        int[][] state = new int[a.length()][b.length()]; 
        // 解决第1行的最大公共子串
        for (int j = 0; j < b.length(); j++) {
            if (a.charAt(0) == b.charAt(j)) {
                state[0][j] = 1;
            } else if (j != 0) {
                state[0][j] = state[0][j - 1];
            } else {
                state[0][j] = 0;
            }
        }
        // 解决第一列的最大公共子串
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) == b.charAt(0)) {
                state[i][0] = 1;
            } else if (i != 0) {
                state[i][0] = state[i - 1][0];
            } else {
                state[i][0] = 0;
            }
        }
        for (int i = 1; i < a.length(); i++) {
            for (int j = 1; j < b.length(); j++) {
                if (a.charAt(i) == b.charAt(j)) { // 字符相同时
                    state[i][j] = max(state[i - 1][j - 1] + 1, state[i - 1][j], state[i][j - 1]); // 从(i-1, j-1)的最大长度+1, 或者(i-1, j), 或者(i, j-1)
                } else {
                    state[i][j] = max(state[i - 1][j - 1], state[i - 1][j], state[i][j - 1]); // 从(i-1, j-1), 或者(i-1, j), 或者(i, j-1)
                }
            }
        }
        return state[a.length() - 1][b.length() - 1];
    }
    private int max(int a, int b, int c) {
        int maxV = Integer.MIN_VALUE;
        if (a > maxV) {
            maxV = a;
        }
        if (b > maxV) {
            maxV = b;
        }
        if (c > maxV) {
            maxV = c;
        }
        return maxV;
    }
}

3.4、思路分析

从(0,0)走到(len(text1)-1, len(text2)-1), 总共要走 len(text1) + len(text2) - 2 步，也就对应着 len(text1) + len(text2) - 2 阶段。每个阶段都有text1向前走或者text2向前走或者两者都向前走三种决策，并且每个阶段都会对应一个状态集合。我们把状态定义为state(i,j), 表示从(0,0)到达(i,j)的最大匹配子序列长度。所以这个问题是一个多阶段决策最优解问题。
重复子问题：从上面回溯算法已经了解到走到(i,j)有多种方法，存在重复子问题。
无后效性：走到(i,j)只能通过(i-1,j),(i,j-1),(i-1,j-1)这三个位置移动过来，类似于只能从往下和往右和往右下三个方向移动，不允许后退，所以，前面阶段的状态确定后，不会被后面阶段的决策所改变，符合“无后效性”。
最优子结构：走到(i,j)只能通过三个位置过来，换句话说就是，state(i,j)可以通过前面三个位置推导出来。
$state(i,j) = max(state(i-1,j-1)+1, state(i-1,j), state(i, j-1)) (text1_i = text2_j)$
$state(i,j) = max(state(i-1,j-1), state(i-1,j), state(i, j-1)) (text1_i \neq text2_j)$

四、数学理论

如上图所示，供应商A要运输一批货物到E公司，两公司中间有一个运输网络，路线中间的结点表示要经过的港口或城市，路线上的数字表示两地间的距离，试求一条运输路径，使所走距离最短。

动态规划有两种解法：逆序解法和顺序解法。

4.1、逆序解法

建模

$k$ （阶段）: 第k个阶段选路的过程，k = 4, 3, 2, 1。
$S_k$ （状态）: 第k个阶段时所处的位置。
$X_k$ （决策变量）：第k个阶段选择的路径。
$V_k$ （阶段指标）：第k个阶段选择的路径对应的路权。
$V_k(S_k,X_k)$ ：指标函数
$f_k(S_k)$ ：最优函数
动态规划基本方程如下：

\begin{cases} f_k(S_k)=min_{(X_k=D_k(S_k),k=4,3,2,1)}{(V_k(S_k,X_k)+f_{k+1}(S_{k+1}))} \\ f_5(S_5)=0 \   \end{cases}

求解

第一步：
- 该最短路问题可划分为四个阶段.
- 边界条件为： $f_5(E)=0$ (说明从E点到E点的最短距离为0)
第二步:
- $k=4，S_4=(D_1,D_2,D_3)$
- $X_4(D_1)=(D_1E),X_4(D_2)=(D_2E),X_4(D_3)=(D_3E)$
- $f_4(D_1)=3+0=3,f_4(D_2)=2+0=2,f_4(D_3)=2+0=2$
第三步:
- $k=3，S_3=(C_1,C_2,C_3,C_4)$
- $X_3C_1)=(C_1D_1E,C_1D_2E),X_3(C_2)=(C_2D_1E,C_2D_2E),X_3(C_3)=(C_3D_2E,C_3D_3E),X_4(C_4)=(C_4D_2E,C_4D_3E)$
- $f_3(C_1)=min(6+3,8+2)=9,f_3(C_2)=min(3+3,5+2)=6,f_3(C_3)=min(3+2,3+2)=5,f_3(C_4)=min(8+2,4+2)=6$
第四步：（同理）
- $f_2(B_1)=9,f_2(B_2)=12$
第五步：（同理）
- $f_1(A)=14$

4.2、顺序解法

建模

$k$ （阶段）: 第k个阶段选路的过程，k = 0, 1, 2, 3, 4。
其它与逆序解法一致
动态规划基本方程

\begin{cases} f_k(S_k)=min_{(X_k=D_k(S_k),k=1,2,3,4)}{(V_k(S_k,X_k)+f_{k-1}(S_{k-1}))} \\ f_0(S_0)=0 \   \end{cases}

求解

求解的过程和逆序解法相反，整体思路一致。

4.3 结论

对于最短路问题，逆序解法可以求出各点到目的地的最短路径和路权，顺序解法可以求出始点到各点的最短路径和路权。一般而言，当给定初始状态时，用逆序解法；当给定结束状态时，用顺序解法。

五、总结

动态规划在算法的解题思路上属于中等偏难的问题，从上面理论的讲解到结合实例的练习，最多只能让你了解动态规划的解题思路，并不代表你可以熟练使用动态规划算法解决实际问题了。

《刻意练习》这本书已经说明了要掌握一项技能的方法。

「刻意练习」的本质是长时工作记忆。具有卓越才能的人，在进行钢琴、象棋等专业活动时，能够调用更大容量的工作记忆。通俗来说，就是他们拥有更大的内存。

这种长时工作记忆可以通过一定的练习来进行激活，通过一定难度的重复练习，在每次练习中收到反馈，不断纠正自己的错误，不断提升大脑的适应能力。