前言

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划和之前的一系列算法不同，它并不是一个算法，也是一种方法，一种思想，通过这种思想，我们可以解决很多问题。

动态规划的例子

动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。上面的这段话，可能理解起来有些麻烦，那么就通过一个例子来简单说明

例子

对于一个简单的斐波那契数列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
如果我们要求第n项，那么应该怎么求呢？

很显然，这个数列的f(n)=f(n-1)-f(n-2),根据我们之前的了解的算法，我们可以写出这样的代码

public long fibonacci(int n){
        if (n == 0){
            return 0;
        }else if (n == 1||n==2){
            return 1;
        }
        return fibonacci(n-1)+fibonacci(n-2);
}

从正确性上来讲，这个代码的确能实现我们的功能，但是如果真的用这种算法，那么当我们计算n=100的时候，我们就会感到绝望，因为它的时间复杂度太大了，这时就说到了我们这篇的主题，动态规划

注意这句话：动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表

之前我们的算法，对于那些已经算出的解，还会重复计算，比如f(n-1)中就包含f(n-2)的那部分，动态规划就是要去掉这些重复的计算，代码如下

public long dynamic(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        }
        long[] f = new long[n];
        f[0] = 0;
        f[1] = f[2] = 1;
        for (int i = 3; i < n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n - 1];
}

下面的这段代码，将之前计算的f(n)的解，都在数组里存储，这样下次再要使用的时候，就可以直接查表，而不需要重复计算，这就是动态规划思想了

动态规划的应用

前面简短的描述了动态规划的例子，接下来就说说动态规划的一些应用，因为动态规划不是一个算法，而是一种思想，所以有很多基于这种思想的算法，接下来就介绍几种

LCS算法（最长公共子序列）

最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。

例如，对于两个字符串

要求它们的最长公共子序列
说明：

1. 假设X1为B，Y1为A

首先，我们看它们的最后一位是否相同，即Xmax和Ymax是否相同，如果相同，那么就在X(max-1)和Y(max-1)里面找，如果不相同，那么就分两种情况，分别在X(max)，Y(max-1)和X(max-1),Y(max)里面找，如图

• 如果不同，那么分两种情况，分别在X{BDCABA},Y{ABCBDA}和X{BDCAB}和{ABCBDAB}里面找
• 如果相同，，假如X最后再添加一个字母B,那么就是在X{BDCABA},Y{ABCBDA}里面找

步骤

1. 首先构造一个二维数组，并且将数组的第一行和第一列赋值为0
2. 从数组的第一行第一列开始，分别开始比较两个字符串，如果当前位置的字符相同，那么就取当前位置的左上加1，如果当前位置的字符不同，那么就取当前位置上方和左方的最大值
3. 不断循环步骤2，直到填完整个表格

这里说说为什么要这样做？
前面说了，如果两个字符串最后一位相同，那么就在X(max-1)，Y(max-1)里面找，如果不同，就分两种情况，分别对应的是X(max)，Y(max-1)和X(max-1),Y(max)

对应到这个图上就是，从最右下角出发

• 如果最右下角的数值比它左边的和上面的都大，说明它是通过左上角加1得到的，那么说明当前位置的字符相同，那么从左上角开始找(从X6Y6回到X5Y5就是这种情况)
• 如果最右下角的数值和它左边的或者上面的数值相同，那么就说明当前位置的字符不同，那么就从大的那个开始找（从X3Y4到X3Y3就是这种情况）,通过图片和之前说的思路结合，我们就可以写出如下代码

代码

//LCS算法
public static void getLCS(String x,String y){
    char[] s1=x.toCharArray();
    char[] s2=y.toCharArray();
    int[][] array=new int[x.length()+1][y.length()+1];
    //先把第一行和第 一列填上零
    for (int i = 0; i < array[0].length; i++) {
        array[0][i]=0;
    }
    for (int i = 0; i < array.length; i++) {
        array[i][0]=0;
    }
    //使用动态规划的方式填入数据
    for (int i = 1; i < array.length; i++) {
        for (int j = 1; j < array[i].length; j++) {
            if(s1[i-1]==s2[j-1]){
                array[i][j]=array[i-1][j-1]+1;
            }else{
                array[i][j]=max(array[i-1][j],array[i][j-1]);
            }
        }
    }

    //一般情况下拿到数组就足够了，这里做演示所以取出所以结果
    //从后往前找到结果
    Stack result=new Stack();
    int i=x.length()-1;
    int j=y.length()-1;
    while((i>=0)&&(j>=0)){
        if(s1[i]==s2[j]){
            result.push(s1[i]);
            i--;
            j--;
        }else{
            if(array[i+1][j-1+1]>array[i-1+1][j+1]){
                j--;
            }else{
                i--;
            }
        }
    }

}

public static int max(int a,int b){
    return (a>b)?a:b;
}

这里右下角的左边和上面都是4，所以说明结果有两种情况，分别是 B C B A 和 B D A B

KMP算法(字符串查找算法)

KMP算法主要用于字符串的查找，例如在一个主文本字符串S内查找一个词W的出现位置,就是这种算法

例如如下字符串S和W,找出W中最长出现的S中的字符串

S: BBC ABCDAB ABCDABCDABDE
W: ABCDABD

一般来说，遇到这种问题我们想到的就是穷举法，但是穷举法在这里效率是及其低下的，这里对于穷举法的说明就不展开了，直接进入主题——KMP算法

思路

1. 首先，按照穷举法的思路一个一个字符的往后对比,直到能够匹配为止
   例如：
   1.1. S1为B，W1为A，不匹配，S比较位后移
   1.2. S2为B，W1为A，不匹配，S比较位后移
   1.3. S3为C，W1为A，不匹配，S比较位后移
2. 当字符开始匹配后，还是和穷举法的思路一样，挨个匹配，直到不匹配
   2.1. S5为A，W1为A，匹配，两者比较位都后移
   2.2. S6为B，W2为B，匹配，两者比较位都后移
   ...
   2.4. S11为空格，W7为D，两者不匹配
3. 这时就需要将S的比较位后移，然后重新比较

如果是按照穷举法的思路，肯定是将S的比较位后移一位，从S6的B字符开始和W1的A字符开始比较，然而KMP算法并不是这样的，下面说说KMP算法的做法
对于上面的比较，因为是从W7开始不匹配的，也就是字符D，那么拿去字符D，处理之后的新字符串
ABCDAB

• 首先，我们要知道，这个字符是W的子串，它已经和S字符进行匹配过了
• 基于上面匹配过的逻辑，我们需要比较这个字符串的前缀和后缀的最大相同数（前缀和后缀跟英语中的字面意思一致）
  那么现在开始比较：
  长度 5：前缀是ABCDA，后缀是BCDAB
  长度 4：前缀是ABCD，后缀是CDAB
  长度 3：前缀是ABC，后缀是DAB
  长度 2：前缀是AB，后缀是AB
  长度 1：前缀是A，后缀是B
  注意，比较要长度从大往小比较，因为要求最大长度的前缀和后缀

显然，这里最大相同的前缀和后缀长度是2，那么对于上述我们需要将前缀移动到后缀对应的位置，如下

S: BBC ABCDAB ABCDABCDABDE
W: --------ABCDABD
P: --------||    对应位置

具体移动的距离 = 已经匹配的长度(6)-前缀和后缀的匹配长度(2) = 4

注意

真正的在比较过程中，并不是移动字符串，而是移动字符串的比较指针，比如S的比较指针，就是指向S当前比较的字符，对于上移动后的位置，用比较指针表示就是

S : BBC ABCDAB ABCDABCDABDE
PS: ----------|    比较指针
W : ABCDABD
PW: --|    比较指针

之前S已经比到了空格，所以比较指针指向空格，W因为前缀和后缀有长度2的相同，所以比较指针从D移到了C，这个移动距离就是4

为什么这样做

因为之前的这些字符串已经比较过一次了，我们在移动之前是这样的

S : BBC ABCDAB ABCDABCDABDE
PS: ----|    比较指针
W : ABCDABD
PW: |    比较指针

我们可以肯定这6个字符串是完全匹配的，基于这个基础上，那么W中和后缀相同的前缀，肯定也和S中现在匹配上的位置想对应，按照这样的对应关系，移动4个长度，这样就避免了重复比较(动态规划的思想就是记录之前求过的解，不重复计算)

S : BBC ABCDAB ABCDABCDABDE
PS: ----------|    比较指针
W : ABCDABD
PW: --|    比较指针

解释完了这次移动的距离，接下来继续比较，现在比较指针指向C的这个位置，而S中对应位置是空格，所以又不匹配，然后继续移动
具体移动的距离 = 已经匹配的长度(2)-前缀和后缀的匹配长度(0) = 2

S : BBC ABCDAB ABCDABCDABDE
PS: ----------|    S比较指针
W : ABCDABD
PW: |    W比较指针

这次比较，现在比较指针指向A的这个位置，而S中对应位置是空格，所以又不匹配，然后继续移动,因为现在没有匹配长度，所以后移1位

S : BBC ABCDAB ABCDABCDABDE
PS: -----------|    比较指针
W : ABCDABD
PW: |    比较指针

重复比较过程，直到发现D和C又不相同，再次移动

S : BBC ABCDAB ABCDABCDABDE
PS: -----------------|    比较指针
W : ABCDABD
PW: ------|    比较指针

具体移动的距离 = 已经匹配的长度(6)-前缀和后缀的匹配长度(0) = 4

10. 再次比较，这次完全匹配

S : BBC ABCDAB ABCDABCDABDE
PS: -----------------|    比较指针
W : ABCDABD
P : --|    比较指针

上面就是整个KMP算法的流程了

最后需要补充一下最大前缀和后缀的计算

最大前后缀长度

对于这个字符串，我们需要计算它匹配长度从2到n的时候，最大前后缀长度

W : ABCDABD

字符串	匹配长度（字符串长度）	最大前后缀长度
AB	2	0
ABC	3	0
ABCD	4	0
ABCDA	5	1
ABCDAB	6	2

我们需要计算这个计算长度为2到length-1时的长度,

思路如下

1. 长度为2时，比较W[0]!=W[1]，即A!=B,即最大前后缀长度为0
2. 长度为3时，比较W[0]!=W[1]，即长度为2是不可能的(即AB!=BC)，然后W[0]!=W[2]，即A!=C，即长度为1也不可能
3. 长度为4时，比较W[0]!=W[1]，W[0]!=W[2]，W[0]!=W[3]，即长度3，2，1全部不可能
4. 长度为5时，比较W[0]!=W[1]，W[0]!=W[2]，W[0]!=W[3]，W[0]==W[4]，即A==A，所以最大前后缀长度为1
5. 长度为5时，比较W[0]!=W[1]，W[0]!=W[2]，W[0]!=W[3]，W[0]==W[4]，W[1]==W[5],即AB==AB,所以最大前后缀长度为2

发现没有，每一步的计算都能用到前一步的计算结果

代码如下

/**
 * 计算回退数
 * @param dest
 * @return
 */
public static int[] kmpNext(String dest) {
    //新建一个数组，保存当前位置的最大前缀后缀相等长度
    int[] next = new int[dest.length()];
    next[0] = 0;
    //i从1开始，即匹配长度为2，j从0开始，即上述中当前前后缀的比较位置
    for (int i = 1, j = 0; i < dest.length(); i++) {
        //j是之前最大前缀后缀相等长度已经比较过的索引
        while (j > 0 && dest.charAt(j) != dest.charAt(i)) {
            //如果不同，那么复用之前比较过的结果，取一个较小的j继续比较
            j = next[j - 1];
        }
        //如果相同，那么i++,j++
        if (dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        //记录当前位置的前后缀最大长度
        //对于字符串ABCDABD，next是{0,0,0,0,1,2,0}
        next[i] = j;
    }

    return next;
}

关于前缀计算这块，如果实在看不懂，可以看这篇博客

KMP代码

public static int kmp(String str, String dest, int[] next) {
    //遍历S字符串的长度，i是S字符串的比较指针，指向当前S字符串比较的位置
    for (int i = 0, j = 0; i < str.length(); i++) {
        //j是W字符串的比较指针，指向当前W字符串比较的位置
        //当S[i]和W[j]不相等时，W的指针需要回退，S的指针不变
        while (j > 0 && str.charAt(i) != dest.charAt(j)) {
            //回退数需要根据前缀和后缀决定
            j = next[j - 1];
        }
        //当S[i]和W[j]指针相同时，i和j都+1
        if (str.charAt(i) == dest.charAt(j)) {
            j++;
        }
        //当完全匹配时，返回开始完全匹配的位置
        if (j == dest.length()) {
            return i - j + 1;
        }
    }
    return 0;
}

Floyd算法(弗洛伊德算法)

Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包

例如：

对于这个图，我们需要求从1个点到另外一个点的最短路径

思路如下

• 距离新增：
  比如从V2到V4的距离是无穷大，从V2到V3再到V4的距离是5+1=6，所以V2到V4的距离是6

• 距离减小：
  比如从V1到V0的距离是9，从V1到V2再到V0的距离是3+2=5，所以V1到V0的距离是5

根据如上两个逻辑，我们可以将图中所有可能成为中间点的顶点遍历一遍，最后得到的距离就是最小距离

核心代码如下

for(k=1;k<=n;k++)  
for(i=1;i<=n;i++)  
for(j=1;j<=n;j++)  
if(e[i][j]>e[i][k]+e[k][j])  
    else [i][j]=e[i][k]+e[k][j];

其中k就是所有可能成为中间点的遍历

考虑到篇幅已经很长了，这里关于Floyd算法就不多说了，如果有疑惑可以看这篇文章