【算法学习】动态规划

动  态  规  划

dynamic programming

那些遗忘过去的人注定要重蹈覆辙。

——乔治·桑塔亚纳（1863-1952）

今天咱们来聊聊动态规划。

动态规划(dynamic programming)是一种基础的算法设计思想。作为一种寻找最优解的通用方法，它是在20世纪50年代由美国数学家Richard Bellman（也就是之前最短路径问题中Bellman ford算法的发明者之一）所发明的。

动态规划的思想实质是分治思想和解决冗余。

与分治法类似的是，我们将原问题分解成若干个子问题，先求解子问题，再从这些子问题的解得到原问题的解。

与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分被重复计算了很多次。如果能够保存已解决的子问题的答案，在需要时再查找，这样就可以避免重复计算、节省时间，也就是解决冗余。

 

实际应用中尝试解决一个问题时，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据），以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。

 

什么是状态？我们在接下来的例子中体会这个概念。

以Fibonacci数列为例，每一个Fibonacci数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。

 

求Fibonacci数列的例子过于简单，为了解决更复杂的问题，我们还需要引入阶段的概念。

阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。

在Fibonacci数列中，每一步会计算得到一个新数字，在这里每一步就是一个阶段，而每个阶段只有一个状态（所以我们会忽略阶段的概念）。

我们再以深度优先搜索走迷宫的过程为例：每一步只能走一格，因为可以向另外三个方向走，所以每一步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，每一步可能处于的位置称为一个状态，下一步可能到达的位置的集合就是这个阶段下所有可能的状态。

整理一下，假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。而我们要求的解一般就是最终阶段的某个状态。

 

了解了阶段、状态的概念后，我们发现，划分阶段、定义状态其实就相当于在划分子问题，也就是在遵循分治思想。

 

而动态规划有别于其他算法的关键在于解决冗余。

我们对问题进行分类，然后针对动态规划能解决的问题进行说明，了解它是如何解决冗余的：

每个阶段只有一个状态->递推；

每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；

每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

在这个分类中我们也可以看出：一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式（也就是得出下一个状态的方式）决定的。

重点看有关动态规划的部分。在这个阐述中，每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到（特别是与后面的阶段无关），包含了两种性质：最优子结构（问题的最优解所包含的子问题的解也是最优的）和重叠子问题（子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到）；而不管之前这个状态是如何得到的，这个性质叫做无后效性。

 

还是以Fibonacci数列为例。在计算到第100项的时候，需要用到第99项和98项（最优子结构，重叠子问题）。这时候你还需要重新计算第99项吗？

不需要，你只需要在第一次计算的时候把它记下来就可以了（无后效性）。

在要用到第99项时，如果没有计算过，就按照递推式计算；如果计算过，直接使用，就像把第99项存储在一个缓存区里一样，这种方法，叫做“记忆化”，是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”：动态规划就是通过这样的方式“记忆”过去，节省每次重新计算的时间。

 

我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

我们将这个表称为最优决策表。最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系依次填写，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

再以最长递增子序列问题为例。

对于长度为N的数组A[n] = {a[0], a[1], a[2], ..., a[n-1]}，将以a[j]结尾的最大递增子序列长度设为L[j]，那么状态转移方程为：

L[j] = max(L[i]) + 1）,   0<=i

我们对每一个A[n]中的元素都计算以他们各自结尾的最大递增子序列的长度，想求a[j]结尾的最大递增子序列的长度时，我们就需要遍历j之前的所有位置i，找出a[i] < a[j]，计算这些i中，能产生最大L[i]的i，之后就可以求出L[j]。我们要求的问题——数组A的最大递增子序列的长度，就是L[n-1]。

在这个问题中，计算每一个L[i]的过程就是一个阶段，对每一个以a[i]为结尾的子序列的长度就是该阶段的一个状态。我们只需要求出每个阶段的一个最优状态，计入表格，就可以一步步得出最终状态，而不需要每次都循环寻找一个递增子序列。

 

所以，寻找符合“最优子结构”的状态和状态转移方程的定义就是我们在利用动态规划解决问题时要做的。在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。

 

需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，即使存在一个有后效性的定义，也不代表该问题一定不适用于动态规划。

 

总结一下解决问题的具体步骤：

    (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

    (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

    (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。

    (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

我们再用动态规划的方法具体解决一个问题：背包问题。

一

0-1背包

有n件物品和容量为m的背包。给出每件物品的重量以及价值，求解：让装入背包的物品重量不超过背包容量的最大价值。

这个问题的特点是每个物品只有一件供你选择放还是不放，也就是只能在0和1之间选择。

设dp[i][j]表示前i件物品，总重量不超过j的最大价值,W[i]表示第i件物品的重量，V[i]表示第i件物品的价值。可得出状态转移方程：

dp[i][j]=max{dp[i-1][j–w[i]]+v [i],dp[i-1][j] }；

 

然后就到了coding time！

//动态规划：01背包问题
#include using namespace std;
int main(){  //输入，N为物品总数量，M为背包容量，v[]表价值，w[]表重量  cout<<"输入物品的数量和背包的最大容量："<<endl;  int N,M;  cin>>N>>M;  cout<<"输入物品的重量、价值："<<endl;   int v[105],w[105];  for (int i=1;i<=N;i++)      cin>> w[i]>>v[i];  //初始化最优决策表   int dp[105][105];  for (int j=0;j<=M;j++)      dp[0][j]=0;  //利用dp方程填表   for (int i=1;i<=N;i++)      for (int j=0;j<=M;j++)    {            if(w[i]<=j) dp[i][j]= (dp[i-1] [j-w[i]]+v[i])>dp[i-1][j]? (dp[i-1] [j-w[i]]+v[i]):dp[i-1][j];            else dp[i][j]=dp[i-1][j];    }  //输出   cout<<"最大价值为"<<dp[N][M];  return 0;}

 

二

完全背包

有n种物品，每种物品无限个，和容量为m的背包。给出每件物品的重量以及价值，求解：让装入背包的物品重量不超过背包容量的最大价值。

特点是每个物品可以无限选用。我们将选择的数量计为k。

 

还是依照之前的定义，直接给出状态转移方程：

dp[i][j] = max{ dp[i-1][ j - w[i] * k] + v[i] * k}; 

（0 <= k * w[i] <= j）

 

code

//动态规划：完全背包问题
#include using namespace std;
int main(){  //输入，N为物品总数量，M为背包容量，v[]表价值，w[]表重量  cout<<"输入物品的数量和背包的最大容量："<<endl;  int N,M;  cin>>N>>M;  cout<<"输入物品的重量、价值："<<endl;   int v[105],w[105];  for (int i=1;i<=N;i++)      cin>> w[i]>>v[i];  //初始化最优决策表       int dp[105][105];  for (int j=0;j<=M;j++)      dp[0][j]=0;  //利用dp方程填表      for (int i=1;i<=N;i++)      for (int j=0;j<=M;j++){         for (int k = 0; k * w[i] <= j; k++){          dp[i][j]= (dp[i-1] [j-w[i]*k]+v[i]*k)>dp[i-1][j]? (dp[i-1] [j-w[i]*k]+v[i]*k):dp[i-1][j];        }      }  //输出   cout<<"最大价值为"<<dp[N][M];  return 0;}

 

三

多重背包

有n件物品和容量为m的背包。给出每件物品的重量，价值，数量。求解：让装入背包的物品重量不超过背包容量的最大价值。

特点是每个物品都有了一定的数量限制。

 

状态转移方程：

dp[i][j] = max{ dp[i-1][ j - w[i] * k ] + v[i] * k }; 

（0 <= k * w[i] <= j，0<=k<=n[i]）

 

code

//动态规划：多重背包问题
#include using namespace std;
int main(){  //输入，N为物品总数量，M为背包容量，v[]表价值，w[]表重量，n[]表数量   cout<<"输入物品的数量和背包的最大容量："<<endl;  int N,M;  cin>>N>>M;  cout<<"输入物品的重量、价值、数量："<<endl;   int v[105],w[105],n[105];  for (int i=1;i<=N;i++)      cin>> w[i]>>v[i]>>n[i];  //初始化最优决策表   int dp[105][105];  for (int j=0;j<=M;j++)      dp[0][j]=0;  //利用dp方程填表   for (int i=1;i<=N;i++)      for (int j=0;j<=M;j++){         for (int k = 0;k * w[i] <= j && k<=n[i]; k++){          dp[i][j]= (dp[i-1] [j-w[i]*k]+v[i]*k)>dp[i-1][j]? (dp[i-1] [j-w[i]*k]+v[i]*k):dp[i-1][j];        }      }  //输出   cout<<"最大价值为"<<dp[N][M];  return 0;}

 

关于背包问题可以有很多拓展，这里只是简单地暴力地运用dp方程实现了问题而已，还有很大的优化提升空间。具体拓展可以看看dd_engi大牛的背包九讲，很详细。

那么，本期就到此为止了。蟹蟹大家的阅读。

#

-The End-

文/今天不太想说话的新手舟

版/真的要考试了的小白舟

码/这期减少了题目量的工人舟

审/老板短短的路走走停停

#