动态规划算法-六虎

一、根本界说

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)$
$(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)$ ：最优函数
动态规划根本方程如下：

{fk(Sk)=min(Xk=Dk(Sk),k=4,3,2,1)(Vk(Sk,Xk)+fk+1(Sk+1))f5(S5)=0\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。
其它与逆序解法共同
动态规划根本方程

{fk(Sk)=min(Xk=Dk(Sk),k=1,2,3,4)(Vk(Sk,Xk)+fk−1(Sk−1))f0(S0)=0\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 定论

关于最短路问题，逆序解法能够求出各点到目的地的最短途径和路权，次序解法能够求出始点到各点的最短途径和路权。一般而言，当给定初始状况时，用逆序解法；当给定结束状况时，用次序解法。

五、总结

动态规划在算法的解题思路上归于中等偏难的问题，从上面理论的讲解到结合实例的操练，最多只能让你了解动态规划的解题思路，并不代表你能够熟练运用动态规划算法处理实践问题了。

《故意操练》这本书现已阐明晰要掌握一项技术的方法。

「故意操练」的本质是长时工作记忆。具有杰出才能的人，在进行钢琴、象棋等专业活动时，能够调用更大容量的工作记忆。浅显来说，便是他们具有更大的内存。

这种长时工作记忆能够经过必定的操练来进行激活，经过必定难度的重复操练，在每次操练中收到反应，不断纠正自己的错误，不断提高大脑的适应能力。

动态规划算法