动态规划DP算法详解

定义

动态规划（dynamic programing）和分治法类似，都是通过组合子问题的解来求解原问题的解。（在经典排序算法中的二路归并排序和快速排序都用到了分而治之的思想-分治法）。

分治法是将原问题划分为没有交集，相互独立的子问题，并分别求解后再进行合并，求出原问题的解。

动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。分治法会做许多不必要的工作，它会反复地求解那些公共子问题。动态规划算法对每个子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都需要重新计算。

动态规划上用来求解最优化问题（optimization problem）。

可以按照下面四个步骤来设计一个动态规划算法：

1、刻画一个最优解的结构特征。

2、递归地定义最优解的值。

3、计算最优解的值，通常采用自底向上的方法。

4、利用计算出的信息构造一个最优解。

对于确定状态转移方程就在第一步和第二步中，首先要确定问题的决策对象，接着对决策对象划分阶段并确定各个阶段的状态变量，最后建立各阶段的状态变量的转移方程。

例如用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用dp[i][j]表示的两个字符串中前 i、 j 个字符的最长公共子序列，我们就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被我们称为状态。状态是描述问题当前状况的一个数字量。首先，它是数字的，是可以被抽象出来保存在内存中的。其次，它可以完全的表示一个状态的特征，而不需要其他任何的辅助信息。最后，也是状态最重要的特点，状态间的转移完全依赖于各个状态本身，如最长递增子序列中，dp[x]的值由 dp[i](i < x)的值确定。若我们在分析动态规划问题的时候能够找到这样一个符合以上所有条件的状态，那么多半这个问题是可以被正确解出的。所以说，解动态规划问题的关键，就是寻找一个好的状态。

最优子结构

用动态规划求解最优化问题的第一步就是刻画一个最优解的结构特征。如果一个问题的最优解包含其子问题的最优解，我们称此问题具有最优子结构性质。因此，某个问题是否适合用动态规划，它是否具有最优子结构性质是一个好的标准。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解。

如何发掘最优子结构的性质？

1、证明问题最优解的第一个组成部分是做出一个选择，而做出这个选择将会产生一个或多个待解的子问题。

2、对一个给定问题，在其可能的第一步选择中，假定已经知道哪种选择才会得到最优解。而我们并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。

3、给定获取的最优解选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。

4、利用“剪切-粘贴(cut and paste)”技术证明作为构成原问题最优解组成部分，每个子问题的解就是它本身的最优解。

反证法：假定子问题的解不是自身的最优解，那么我们就可以从原问题中剪切掉这些非最优解，将最优解粘贴进去，从而得到原问题一个更优的解，这个解与最初的解的前提假设矛盾。

刻画子问题空间的经验

保持子问题空间尽量简单，只在必要时才扩展它。例如下一节的例子，求钢条切割的最大收益问题中，子问题空间包含的问题为：对每个i值，长度为i的钢条最优切割问题。

对于不同问题领域，最优子结构的不同体现在两个方面：

原问题的最优解中涉及到多个子问题。
在确定最优解使用哪些子问题时，需要考察多少种选择。

重叠子问题

适合用动态规划方法求解最优化问题的第二个性质是子问题的空间必须足够小，即问题的递归算法会反复地求解相同的子问题，而不是一直生成新的子问题。动态规划算法会对重叠的子问题只求解一次，并保存在一张表里，需要用的时候直接查表即可，每次查表的时间代价为常量O(1)。

核心问题

动态规划的核心是状态和状态转移方程。

在记忆化搜索中，可以为正在处理的表项声明一个引用，简化对它的读写操作；

动态规划解决的是多阶段决策问题；

1	初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

和分治法最大的区别在于：适合于用动态规划的问题，经过分解以后得到的子问题往往不是相互独立的（即下一个子阶段的求解是建立在上一个子阶段的基础之上，进行进一步的求解，而不是相互独立的问题）

动态规划问题一般由难到易分为一维动态规划，二维动态规划，多维动态规划，以及多变量动态规划问题。其中多维动态规划问题又可以进行降维。动态规划问题求解的最重要的一步就是求解出 状态转移方程

特性

最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理.
无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关
有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势，动态规划可以避免多次计算）

动态规划的解题核心主要分为两步：

第一步：状态的定义
第二步：状态转移方程的定义

在这里，我们为了避免混淆用“状态”这个词来替代“问题”这个词。“问题”表示的含义类似：题目、要求解的内容、题干中的疑问句这样的概念。状态表示我们在求解问题之中对问题的分析转化。

第一步：状态的定义

有的问题过于抽象，或者过于啰嗦干扰我们解题的思路，我们要做的就是将题干中的问题进行转化（换一种说法，含义不变）。转化成一系列同类问题的某个解的情况，比如说：

题目：求一个数列中最大连续子序列的和。

我们要将这个原问题转化为：

状态定义：Fk是第k项前的最大序列和，求F1～FN中最大值。

通过换一种表述方式，我们清晰的发现了解决问题的思路，如何求出F1～FN中的最大值是解决原问题的关键部分。上述将原问题转化成另一种表述方式的过程叫做：状态的定义。这样的状态定义给出了一种类似通解的思路，把一个原来毫无头绪的问题转换成了可以求解的问题。

第二步：状态转移方程的定义

在进行了状态的定义后，自然而然的想到去求解F1～FN中最大值。这也是状态定义的作用，让我们把一个总体的问题转化成一系列问题，而第二步：状态转移方程的定义则告诉我们如何去求解一个问题，对于上述已经转换成一系列问题我们要关注的点就在于：如何能够用前一项或者前几项的信息得到下一项，这种从最优子状态转换为下一个最优状态的思路就是动态规划的核心。
对于上面的例子题目来说，状态转移方程的定义应该是：

Fk=max{Fk-1+Ak,Ak}
Fk是前k项的和，Ak是第k项的值

仔细思考一番，我们能够得到这样的结论，对于前k个项的最大子序列和是前k-1项的最大子序列和Fk与第k项的和、或者第k项两者中较大的。如果大家还是不能理解这个原理建议用演算纸自己计算一番，这里就不过多赘述了。这种状态转移的思路就是DP的核心。

状态转移方程

动态规划中当前的状态往往依赖于前一阶段的状态和前一阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui，那么第i+1阶段的状态Si+1也就确定了。所以解决动态规划问题的关键就是确定状态转移方程，一旦状态转移方程确定了，那么我们就可以根据方程式进行编码。

各种模型的状态转移方程汇总如下：

1、最长公共子串

假设两个字符串为str1和str2，它们的长度分别为n和m。d[i][j]表示str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的子问题进行求解。状态转移方程如下：

dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
dp[i][j] = 0; (str1[i] != str2[j])

因为最长公共子串要求必须在原串中是连续的，所以一但某处出现不匹配的情况，此处的值就重置为0。

详细代码请看最长公共子串。

#include "stdafx.h"
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;

#define MAXSIZE 100
char str1[MAXSIZE];
char str2[MAXSIZE];

int dp[MAXSIZE][MAXSIZE];
//'y'代表str1[i] = str2[j];'n'反之
char path[MAXSIZE][MAXSIZE];

void printComStr(int i, int j)
{
    if (path[i][j] == 'n' || i == 0 || j == 0)
        return;
    if (path[i][j] == 'y')
    {
        printComStr(i - 1, j - 1);
        cout << str1[i - 1];
    }


}

int main()
{
    int n, m;
    int indexi, indexj;
    int ans = 0;
    cin >> str1 >> str2;
    n = strlen(str1);
    m = strlen(str2);
    for (int i = 0; i <= n;i++)
    for (int j = 0; j <= m; j++)
    {
        dp[i][j] = 0;
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (str1[i - 1] == str2[j - 1])
        {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            path[i][j] = 'y';
        }
        else
        {
            dp[i][j] = 0;
            path[i][j] = 'n';
        }
    }
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (ans < dp[i][j])
        {
            ans = dp[i][j];
            indexi = i;
            indexj = j;
        }
    }
    cout << ans << endl; 
    cout << indexi << ' ' << indexj << endl;
    printComStr(indexi, indexj);
}

2、最长公共子序列

区分一下，最长公共子序列不同于最长公共子串，序列是保持子序列字符串的下标在str1和str2中的下标顺序是递增的，该字符串在原串中并不一定是连续的。同样的我们可以假设dp[i][j]表示为字符串str1的前i个字符和字符串str2的前j个字符的最长公共子序列的长度。状态转移方程如下：

dp[0][j] = 0; (0<=j<=m)
dp[i][0] = 0; (0<=i<=n)
dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])
dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1])

详细代码请看最长公共子序列。

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

#define MAXSIZE 101
char str1[MAXSIZE];
char str2[MAXSIZE];
//'l'表示dp[i][j] = dp[i][j] = dp[i - 1][j];
//‘q’表示dp[i][j] = dp[i][j] = dp[i - 1][j];
//'u'表示dp[i][j] = dp[i][j - 1];
char path[MAXSIZE][MAXSIZE];
int dp[MAXSIZE][MAXSIZE];

void printLCS(int i, int j)
{
    if (i == 0 || j == 0)
        return;
    if (path[i][j] == 'q')
    {
        printLCS(i - 1, j - 1);
        cout << str1[i-1] << ' ';
    }
    else if (path[i][j] == 'u')
        printLCS(i - 1, j);
    else
        printLCS(i, j - 1);
    
} 

int main()
{
    int n, m;
    cin >> str1 >> str2;
    n = strlen(str1);
    m = strlen(str2);
    //初始化
    for (int i = 0; i < n;i++)
    for (int j = 0; j < m; j++)
        dp[i][j] = 0;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        if (str1[i - 1] == str2[j - 1])
        {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            path[i][j] = 'q';
        }
        else
        {
            if (dp[i - 1][j] >= dp[i][j - 1])
            {
                dp[i][j] = dp[i - 1][j];
                path[i][j] = 'u';
            }
            else
            {
                dp[i][j] = dp[i][j - 1];
                path[i][j] = 'l';
            }

        }
    }
    cout << dp[n][m] << endl;
    printLCS(n, m);
    return 0;
}

3、最长递增子序列（最长递减子序列）

因为两者的思路都是一样的，所以只给出最长递增子序列的状态转移方程。假设有序列{a1,a2,…,an}，我们求其最长递增子序列长度。按照递推求解的思想，我们用F[i]代表若递增子序列以ai结束时它的最长长度。当 i 较小，我们容易直接得出其值，如 F[1] = 1。那么，如何由已经求得的 F[i]值推得后面的值呢？假设，F[1]到F[x-1]的值都已经确定，注意到，以ax 结尾的递增子序列，除了长度为1的情况，其它情况中，ax都是紧跟在一个由 ai(i < x)组成递增子序列之后。要求以ax结尾的最长递增子序列长度，我们依次比较 ax 与其之前所有的 ai(i < x)，若ai小于 ax，则说明ax可以跟在以ai结尾的递增子序列之后，形成一个新的递增子序列。又因为以ai结尾的递增子序列最长长度已经求得，那么在这种情况下，由以 ai 结尾的最长递增子序列再加上 ax 得到的新的序列，其长度也可以确定，取所有这些长度的最大值，我们即能得到 F[x]的值。特殊的，当没有ai(i < x)小于ax，那么以 ax 结尾的递增子序列最长长度为1。即F[x] = max{1,F[i]+1|ai<ax && i<x}。

详细代码请看最长递增子序列。

#include <iostream>
using namespace std;
const int MAXSIZE = 10;
const int MIN = 0;
int arr[] = { 1, 4, 3, 2, 6, 5 };
int F[MAXSIZE];
int main()
{
    int maxLen = MIN;
    memset(F, 0, MAXSIZE);
    F[0] = 1;
    for (int i = 1; i < 6; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j] && maxLen < F[j])
            {
                maxLen = F[j];
            }
        }
        F[i] = maxLen + 1;
    }

    for (int k = 0; k < 6; k++)
        cout << F[k] << ' ';
    cout << endl;
}

4、最大子序列和的问题

假设有序列{a1,a2,…,an}，求子序列的和最大问题，我们用dp[i]表示以ai结尾的子序列的最大和。

dp[1] = a1; (a1>=0 && i == 1)

dp[i] = dp[i-1]+ai; (ai>=0 && i>=2)

dp[i] = 0; (dp[i-1] + ai <=0 && i>=2)

详细代码请看最大子序列的和。

#include <iostream>
using namespace std;

#define MAXSIZE 100

int a[MAXSIZE];
int dp[MAXSIZE];
int max = 0;
int main()
{
    int n;
    cin >> n;
    memset(dp, 0, MAXSIZE);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        if (dp[i-1] + a[i] > 0)
        {
            dp[i] = dp[i - 1] + a[i];
        }
        else
        {
            dp[i] = 0;
        }
        if (max < dp[i])
            max = dp[i];
    }
    cout << max << endl;
    return 0;
}

5、数塔问题（动态搜索）

给定一个数组data[n][m]构成一个数塔求从最上面走到最低端经过的路径和最大。可以假设dp[i][j]表示走到第i行第j列位置处的最大值，那么可以推出状态转移方程：

1	dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} + data[i][j];

for(i=n-1;i>=1;i--){
     for(j=1;j<=i;j++){
         dp[i][j]=max{dp[i-1][j-1],dp[i-1][j]}+s[i][j]
     }
}

6、（01）背包问题

这是一个经典的动态规划问题，另外在贪心算法里也有背包问题，至于二者的区别在此就不做介绍了。

假设有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是c[i]，将哪些物品装入背包可使价值总和最大？

每一种物品都有两种可能即放入背包或者不放入背包。可以用dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值，则状态转移方程可以推出如下：

1	dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};

for (int i = 1;i <= N;i++) //枚举物品  
    {  
        for (int j = 0;j <= V;j++) //枚举背包容量  
        {  
            f[i][j] = f[i - 1][j];  
            if (j >= v[i])  
            {  
                f[i][j] = Max(f[i - 1][j],f[i - 1][j - v[i]] + c[i]);  
            }  
        }  
    }

说明

01背包问题与背包问题的区别在于，01背包，物品的选择只有两种一种是拿，另一种是不拿，而背包问题在于，物品可以只取一部分。所以01背包问题不能用贪心算法解决。

以dp[i][j]表示用i种物品，重量为j表示所取得的价值。

对于第i种物品，如果第i种物品重量大于j，就证明第i种物品肯定不能取，这时的dp[i][j]=dp[i-1][j]

如果第i种物品重量小于j，那就会出现两种情况，采用i的话，物品价值dp[i][j]=采用前面的i-1种物品，所占用的重量为j-i.getweight,所产生的价值+第i 种物品的价值，。如果不采用i，价值为dp[i-1][j]。换成数学表达式就是dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);

比如当i=5,j=10时，dp[5][10]就代表了所取得的最大价值。到这里我们就完成了任务的一半，接下为我们要寻找到底哪些物品放入了背包，从前面的表达式我们可以发现，当dp[i][j]=dp[i-1][j-weight]时，这时为i的物品就会放入背包，所以我们从结果，开始往回走，遇到这种情况，就说明有物品放入背包，然后物品数减1，重量减去为i的重量，继续，最后就能求出哪 些物品放入背包了。

JAVA代码

public class Test {
    public static void main(String[] args) {
         int allweight=12;  //总价值      
         int num=8;   //物品
          bao[] baos=new bao[num+1];
          baos[1]=new bao(2, 13);
          baos[2]=new bao(1, 10);
          baos[3]=new bao(3, 24);
          baos[4]=new bao(2, 15);
          baos[5]=new bao(4, 28);
          baos[6]=new bao(5, 33);
          baos[7]=new bao(3, 20);
          baos[8]=new bao(1, 8);
          int[][] dp=new int[num+1][allweight+1];
          //构成动态规划表
          for(int i=0;i<=num;i++)
          {
              for(int j=0;j<=allweight;j++)
              {
                  if(i==0||j==0)
                  {
                      dp[i][j]=0;
                  }else {
                      if (j<baos[i].getWeight()) {
                        dp[i][j]=dp[i-1][j];
                    }else {
                        int value=baos[i].getValue();
                        int weight=baos[i].getWeight();
                        dp[i][j]=Math.max(dp[i-1][j-weight]+value,dp[i-1][j]);
                    }
                }
                  System.out.println("dp"+"["+i+"]"+"["+j+"]"+dp[i][j]);
              }
          }
          int m=num;
          int n=allweight;
          int all=dp[m][n];
          //寻找哪些物品放入背包
           while(all>=0)
           {
               if (m>0&&dp[m][n]==dp[m-1][n]) {
                   m=m-1;
                }else {
                    System.out.println(baos[m]+"加入背包");
                    m=m-1;
                    if (m==0) {
                        return;
                    }else {
                        n=n-baos[m].getWeight();
                        all=all-baos[m].getWeight();
                    }
                }
           }
    }
}

可以参照动态规划 - 0-1背包问题的算法优化、动态规划-完全背包问题、动态规划-多重背包问题、01背包问题

7、矩阵连乘（矩阵链问题）-参考《算法导论》

例如矩阵链<A1,A2,A3>,它们的维数分别为10100,1005,550，那么如果顺序相乘即((A1A2)A3)，共需101005 + 10550 = 7500次乘法，如果按照(A1(A2A3))顺序相乘，却需做100550 + 10100*50 = 75000次乘法。两者之间相差了10倍，所以说矩阵链的相乘顺序也决定了计算量的大小。

我们用利用动态规划的方式(dp[i][j]表示第i个矩阵至第j个矩阵这段的最优解,还有对于两个矩阵A(i,j)B(j,k)则需要ij*k次乘法)，推出状态转移方程：

1
2
3

dp[i][j] = 0; (i ==j，表示只有一个矩阵，计算次数为0)
dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]}; (i<j && i<=k<j)            
dp[1][n]即为最终求解.

#define MAXSIZE 100

int dp[MAXSIZE][MAXSIZE];//存储最小的就算次数
int s[MAXSIZE][MAXSIZE];//存储断点，用在输出上面

int i, j, tmp；

for (int l = 2; l <= n; l++){//j-i的长度,由于长度为1是相同的矩阵那么为0不用计算
    for (i = 1; i <= n - l + 1; i++){//由于j-i =l - 1 , 那么j的最大值为n，所以i上限为 n - l+1;
        j = i + l - 1;//由于j-i = l - 1 , 那么j = l+i-1
        dp[i][j] = dp[i + 1][j] + r[i] * c[i] * c[j];//初始化，就是k = i；
        s[i][j] = i;
        for (k = i + 1; k < j; k++){//循环枚举k i < k < j
            tmp = dp[i][k] + dp[k + 1][j] + r[i] * c[k] * c[j];
            if (dp[i][j] > tmp){
                dp[i][j] = tmp;//更新为最小值
                s[i][j] = k;
            }
        }
    }
}
//递归调用输出
void output(int i, int j){
    if (i == j){
        printf("A%d", i);//当两个相等的时候就不用继续递归就输出A
        return;//返回上一层
    }

    else{
        printf("(");
        output(i, s[i][j]);
        printf(" x ");
        output(s[i][j] + 1, j);
        printf(")");
    }
}

总结

太难了，没事多来看看示例希望早日彻底吃透！

参考文章:
参考链接1
参考链接2