概述
动态规划在计算机科学领域，成为一种通用的算法设计技术用来求解多阶段决策最优化问题
最优化问题
有 n 个输入，问题的解由这 n 个输入的一个子集组成，这个子集必须满足某些事先给定的约束条件，满足约束条件的解称为问题的可行解
为了衡量可行解的优劣，通常以函数的形式给出一定的评价标准，这些标准函数称为目标函数（也称评价函数），目标函数的极值（极大或极小）称为最优值，使目标函数取得极值的可行解称为最优解
多阶段决策过程
一个决策序列在不断变化的状态中产生的过程。具有n个输入的最优化问题，其求解过程划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。
动态规划的求解过程
- 划分子问题
将原问题的求解过程划分为若干个阶段，每个阶段对应一个子问题，并且子问题之间具有重叠关系； - 动态规划函数
根据子问题之间的重叠关系找到子问题满足的递推关系式，这是动态规划法的关键； - 填写表格
根据动态规划函数设计表格，以自底向上的方式计算各个子问题的最优值并填表，实现动态规划过程
动态规划过程只能求得问题的最优值，如果要得到使目标函数取得极值的最优解，通常在动态规划过程中记录每个阶段的决策，再根据最优决策序列通过回溯构造最优解
例题
网格上的最短路径
问题
给定一个包含正整数的 m×n 网格，每次只能向下或者向右移动一步，定义路径长度是路径上经过的整数之和。请找出一条从左上角到右下角的路径，使得路径长度最小
分析
- 考虑初始子问题，对于第一行/列，只有一条路径，路径长度就是该行/列上所有整数之和有：\[\begin{cases} f(i,1)=\sum_{j=1}^i a_{i,j}=d(i,1)+A[i-1,1] \\ f(1,j)=\sum_{i=1}^j a_{i,j}=d(1,j)+A[1,j-1] \end{cases}\]
- 考虑重叠子问题，对于非第一行/列的网格，最短路径长度等于其上方相邻网格与其左方相邻网格的最短径长度的较小值加上当前网格的值，有：\[f(i,j)=min\{d(i-1,j),d(i,j-1)\}+A_{i,j} \]
- 为了得到网格的最短路径，设p(m, n)记录每个网格的最短路径是由上方还是左方到达
实现
int minPath(int **a,int m,int n){
int dp[m][n];
int path[m][n];
dp[0][0]=a[0][0];
for(int i=1;i<m;i++){
a[i][0]+=a[i-1][0];
path[i][0]=1;
}
for(int i=1;i<n;i++){
a[0][i]+=a[0][i-1];
path[0][i]=0;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
a[i][j]+=min(a[i-1][j],a[i][j-1]);
if(a[i-1][j]<a[i][j-1]){
path[i][j]=1;
}
else{
path[i][j]=0;
}
}
}
//输出
int i=m-1,j=n-1;
while(i>=0&&j>=0){
cout<<i<<"--"<<j<<endl;
if(path[i][j]==1) i--;
else j--;
}
}
最长公共子序列
问题
子序列：给定一个序列，从中去掉若干个元素，剩下的元素组成的序列称为原序列的子序列。
序列\(X=(a, b, c, b, d, a, b)\)，序列\((b, c, d, b)\)是 \(X\)的一个长度为 4 的子序列，相应的递增下标序列为\((2, 3, 5, 7)\)。
公共子序列：给定两个序列 \(X=(x_1, x_2, ..., x_m)\) 和 \(Y=(y_1, y_2, ..., y_n)\)，求 \(X\) 和 \(Y\) 的最长公共子序列，即求一个序列 \(Z=(z_1, z_2, ..., z_k)\)，使得 \(z_1, z_2, ..., z_k\) 是 \(X\) 和 \(Y\) 的子序列，且 \(k\) 最大。
分析：
- 考虑初始子问题，对于两个空序列，最长公共子序列长度为0
- 考虑重叠子问题，设\(L(i, j)（1 ≤ i ≤ m, 1 ≤ j ≤n）\)表示子序列 \(X_i\) 和 \(Y_j\) 的最长公共子序列的长度，存在以下两种情况：
- \(x_i = y_j\)
- \(x_i≠y_j\)
则有如下动态规划函数\[L(i,j)=\begin{cases} 0 & i=0,j=0 \\ L(i-1,j-1)+1 & i,j>0,x_i=y_j \\ max\{L(i-1,j),L(i,j-1)\} & i,j>0,x_i≠y_j \end{cases}\]
- 为了得到最长公共子序列，设\(p(i, j)\)记录每个网格的最长公共子序列是由上方还是左方到达，记录决策为\[p(i,j)=\begin{cases} 0 & i=0,j=0 \\ 1 & i,j>0,x_i=y_j \\ 2 & i,j>0,x_i>y_j\\ 3 & i,j>0,x_i<y_j \end{cases}\]
序列\(X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)\)，动态规划法求解最长公共子序列的过程如下
实现
int commonOrder(char *a, char *b, int n, int m,char *c){
int L[n+1][m+1]={0};
int S[n+1][m+1]={0};
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0){
L[i][j]=0;
S[i][j]=0;
}
else if(a[i-1]==b[j-1]){
L[i][j]=L[i-1][j-1]+1;
S[i][j]=1;
}
else if(L[i-1][j]>=L[i][j-1]){
L[i][j]=L[i-1][j];
S[i][j]=2;
}
else{
L[i][j]=L[i][j-1];
S[i][j]=3;
}
}
}
int i=n,j=m,k=L[n][m]-1;
while(i>0 && j>0){
if(S[i][j]==1){
c[k]=a[i-1];
i--;
j--;
k--;
}
else if(S[i][j]==2){
i--;
}
else{
j--;
}
}
return L[n][m];
}
0/1背包问题
问题
有 \(n\) 个物品，每个物品的重量为 \(w_i\)，价值为 \(v_i\)，背包的容量为 \(W\)，求解将哪些物品装入背包可使物品总重量不超过背包容量，且总价值最大。
分析
- 考虑初始子问题，对于 \(n=0\)，最大价值为0
- 考虑重叠子问题，设 \(V(i, j)\) 表示前 \(i\) 个物品中选择若干个装入容量为 \(j\) 的背包中，使得总价值最大，存在以下两种情况：
- \(w_i > j\)，则 \(V(i, j)=V(i-1, j)\)
- \(w_i ≤ j\)，则 \(V(i, j)=max\{V(i-1, j), V(i-1, j-w_i)+v_i\}\)
- 记录决策，设 \(S(i, j)\) 表示 \(V(i, j)\) 的值是由 \(V(i-1, j)\) 还是 \(V(i-1, j-w_i)+v_i\) 得到的，记录决策为\[S(i,j)=\begin{cases} 0 & V(i,j)=V(i-1,j) \\ 1 & i,V(i,j)＞V(i-1,j) \\ \end{cases}\]
实现
int knapSack(int w[],int v[],int n,int C,int x[]){
int V[n+1][C+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=C;j++){
if(i==0||j==0){
V[i][j]=0;
}
else if(w[i-1]<=j){
V[i][j]=max(V[i-1][j],V[i-1][j-w[i-1]]+v[i-1]);
}
else{
V[i][j]=V[i-1][j];
}
}
}
int i=n,j=C;
while(i>0&&j>0){
if(V[i][j]!=V[i-1][j]){
x[i-1]=1;
j-=w[i-1];
}
i--;
}
return V[n][C];
}
多段图最短路径问题
问题
W先生每天驾车去公司上班。W先生的住所位于A，公司位于F，线段代表公路，交叉点代表路口，线段上的数字代表两路口之间的平均行驶时间。请为W先生确定一条最省时的上班路线
分析
- 考虑初始子问题，对于 \(i=0\)，最短路径为 \(d_0=0\)
- 考虑重叠子问题，设 \(d_i\) 表示从 \(A\) 到 \(i\) 的最短路径，
\(d_i=min\{d_j+c_{ji}\}\)，其中 \(j\) 为 \(i\) 的前驱节点 - 记录决策，设 \(p_i\) 表示 \(d_i\) 的值是由 \(d_j+c_{ji}\) 得到的，记录决策为 \(p_i=j\)
实现
int shortestPath(int **a,int n){
int cos[n]={0};
int path[n]={0};
path[0]=-1;
for(int i=1;i<n;i++){
cos[i]=100000;
for(int j=0;j<i;j++){
if(cos[i]>cos[j]+a[j][i]){
cos[i]=cos[j]+a[j][i];
path[i]=j;
}
}
}
for(int i=n-1;i>=0;i--){
cout<<path[i]<<" ";
i=path[i];
}
return cos[n-1];
}
TSP问题
问题
TSP问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短
分析
如
\[ \left[ \begin{matrix} \infty & 3 & 6 & 7 \\ 5 & \infty & 2 & 3 \\ 6 & 4 & \infty & 2 \\ 3 & 7 & 5 & \infty \\ \end{matrix} \right] \]- 考虑初始子问题，对于 \(i=0\)，设 \(d(k,{})\)从\(k\)出发回到\(i\)的最短路径，\(d(k,{})=c_{ki}\)
在这个图中，- \(d(1,\{\})=c_{10}=5\)
- \(d(2,\{\})=c_{20}=6\)
- \(d(3,\{\})=c_{30}=3\)
- 考虑重叠子问题，设 \(d(k,{V-k}\) 表示从 \(k\) 出发回到 \(i\) 的最短路径，\(d(k,{V-k})=min\{d(j,{V-k-j})+c_{ji}\}\)，其中 \(j\) 为 \(V-k\) 的一个元素
- 对于第一个阶段，有
- \(d(1,\{2\})=c_{12}+d(2,\{\})=2+6=8\)(从1到2，再从2到0)
- \(d(1,\{3\})=c_{13}+d(3,\{\})=3+3=6\)(从1到3，再从3到0)
- \(d(2,\{1\})=c_{21}+d(1,\{\})=4+5=10\)(从2到1，再从1到0)
- ···
- 对于第二个阶段，有
- \(d(1,{2,3})=\min\{d(2,\{2,3\})+c_{12},d(3,\{2,3\})+c_{13}\}=\min\{2+5,3+11\}=7\)
- \(d(2,{1,3})=\min\{d(1,\{1,3\})+c_{21},d(3,\{1,3\})+c_{23}\}=\min\{4+6,2+12\}=10\)
- \(d(3,{1,2})=\min\{d(1,\{1,2\})+c_{31},d(2,\{1,2\})+c_{32}\}=\min\{7+8,5+9\}=14\)
- 对于第三个阶段，有
- \(d(0,{1,2,3})=\min\{d(1,\{1,2,3\})+c_{10},d(2,\{1,2,3\})+c_{20},d(3,\{1,2,3\})+c_{30}\}=0\)
- 对于第一个阶段，有
- 决策，设 \(p_i\) 表示 \(d_i\) 的值是由 \(d_j+c_{ji}\) 得到的，记录决策为 \(p_i=j\)
实现
void TSP(int n,int** graph,int location){
//构建二维数组[i,2^n]，j模拟集合个数
int **D = new int*[n+1]; //建行0～n，为方便理解和表示，第0行未使用
int **Rec = new int*[n+1]; //建立Rec
for(int i=1;i<=n;i++){
//建列表示集合
D[i] = new int [(int)pow(2,n)];
Rec[i] = new int [(int)pow(2,n)];
}
//初始化D、Rec
for(int i=1;i<=n;i++){
D[i][0]=graph[i][location]; //D[i,{}]
Rec[i][0]= -1;
for(int j=1;j<=(int)pow(2,n)-1;j++){
D[i][j]=N;
Rec[i][j] = -1;
}
}
//动态规划
for(int j=1;j<=(int)pow(2,n)-1;j++){ //对每一列求解
for(int i=1;i<=n;i++){ //每一行找最短路径
int min = N;
if(((int)pow(2,i-1) & j) == 0){ //顶点集不能包含i
int length = N;
for(int k=1;k<=n;k++){
if((int)pow(2,k-1) & j ){ //若顶点在集合中
length = graph[i][k] + D[k][j-(int)pow(2,k-1)];
if(length < min){
min = length;
D[i][j] = min;
Rec[i][j] = k;//局部最优决策
}
}
}
}
}
}
cout<<"最短长度："<<D[location][(int)pow(2,n)-1-(int)pow(2,location-1)]<<endl;//最短路径长度
cout<<"最短路径为："<<location;
int row = location;
int column = (int)pow(2,n)-1-(int)pow(2,row-1);
while(column > 0){
cout<< "->"<<Rec[row][column];
row = Rec[row][column];
column -= (int)pow(2,row-1);
}
cout<<"->"<<location<<endl;
}
近似串匹配
问题
设样本P=p1p2…pm，文本T=t1t2…tn，假设样本是正确的，对于一个非负整数 K，样本 P 和文本 T 的 K-近似匹配（K-approximate match）是指 P 和 T 在所有对应方式下的最小编辑错误数。这里的编辑错误（也称差别）是指下列三种情况之一：
- 修改：T 与 P 中对应字符不同
- 删去：T 中含有一个未出现在 P 中的字符
- 插入：T 中不含有在 P 中出现的一个字符
分析
设\(D(m,n)\)为样本P的前m个字符和文本T的前n个字符的最小编辑错误数。则有
- 初始子问题\[ D(0,0)=0\\ D(0,j)=j\\ D(i,0)=i \]
- 考虑重叠子问题，有以下三种情况
- \(D(i,j)=D(i-1,j-1)\)，当 \(p_i=t_j\)
- 当 \(p_i\neq t_j\) 时，有
- \(D(i,j)=D(i-1,j-1)+1\)，修改
- \(D(i,j)=D(i-1,j)+1\)，删去
- \(D(i,j)=D(i,j-1)+1\)，插入
- 因此过程为\[D(i,j)=\begin{cases} D(i-1,j-1), & p_i=t_j\\ \min\{D(i-1,j-1)+1,D(i-1,j)+1,D(i,j-1)+1\}, & p_i\neq t_j \end{cases} \]
int ASM(char p[],int m,char t[],int n){
int d[m][n];
for(int i=0;i<m;i++) d[i][0]=i;
for(int j=0;j<n;j++) d[0][j]=j;
for(int j=1;j<n;j++){
for(int i=1;i<m;i++){
if(p[i]==t[j]) d[i][j]=d[i-1][j-1];
else d[i][j]=min(d[i-1][j-1],min(d[i-1][j],d[i][j-1]))+1;
}
}
return d[m-1][n-1];
}
最佳二叉查找树
问题
最优二叉查找树是以 n 个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即\(\displaystyle \sum_{i=1}^{n}p_i\times c_i\)
分析
设有二叉树\(T(1,n)\)，平均查找次数为\(C(1,n)\)，则有
- 考虑初始子问题，集合只有一个g一个元素时，\(C(1,1)=p_1\)
- 考虑重叠子问题\[ C(i,j)=min_{i\leq k\leq j}\{p_k\times1+\sum_{s=i}^{k-1}p_i\times(r_s在T(i,k-1)中的层数+1)+\sum_{s=k+1}^{j}p_i\times(r_s在T(k+1,n)中的层数+1)\} 选择任意的k做根节点\\ =min_{i\leq k\leq j}\{p_k\times1+\sum_{s=i}^{k-1}p_i\times(r_s在T(i,k-1)中的层数)+\sum_{s=i}^{k-1}p_i+\sum_{s=k+1}^{j}p_i\times(r_s在T(k+1,n)中的层数)+\sum_{s=k+1}^{j}p_i\}\\ =min_{i\leq k\leq j}\{\sum_{s=i}^j p_i+\sum_{s=i}^{k-1}p_i\times(r_s在T(i,k-1)中的层数)+\sum_{s=k+1}^{j}p_i\times(r_s在T(k+1,n)中的层数)\}\\ =min_{i\leq k\leq j}\{C(i,k-1)+C(k+1,j)+\sum_{s=i}^j p_i\} \]即动态规划函数为\[ C(i,j)=\begin{cases} 0, & i>j\\ p_i, & i=j\\ min_{i\leq k\leq j}\{C(i,k-1)+C(k+1,j)+\sum_{s=i}^j p_i\}, & i<j \end{cases} \]
实现
double optimalBST(double p[],int n){
double c[n+1][n+2]={0};
//对角线
for(int i=1;i<=n;i++){
c[i][i]=p[i];
}
double min;
double sum=0;
for(int i=1;i<n;i++){
for(int j=i+1;j<n-i;j++){
min=100000;
for(int k=i;k<=j;k++){
sum+=p[k];
if(c[i][k-1]+c[k+1][j]<min){
min=c[i][k-1]+c[k+1][j];
}
}
c[i][j]=min+sum;
}
}
return c[1][n];
}
塔数问题
问题
从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层，要求找出一条路径，使得路径上的数值和最大。
分析
- 考虑初始子问题，最底层的最大值为自身
- 考虑叠加子问题，从最底层开始，每个结点的最大值为自身加上左右子结点的最大值\[f(i,j)=\max\{f(i+1,j),f(i+1,j+1)\}+a(i,j) \]
- 记录决策：记录每个结点的最大值是由左子结点还是右子结点决定的\[p[i,j]=\begin{cases} j &a(i+1,j)>a(i+1,j+1)\\ j+1 &a(i+1,j)\leq a(i+1,j+1) \end{cases}\]
实现
int dataTower(int **t,int n){
int maxAdd[n][n]={0};
int path[n][n]={0};
//从底层开始，初始子问题
for(int i=0;i<n;i++){
maxAdd[n-1][i]=t[n-1][i];
}
//从底层开始，逐层向上求解
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
if(maxAdd[i+1][j]>maxAdd[i+1][j+1]){
maxAdd[i][j]=maxAdd[i+1][j]+t[i][j];
path[i][j]=j;
}
else{
maxAdd[i][j]=maxAdd[i+1][j+1]+t[i][j];
path[i][j]=j+1;
}
}
}
//输出最优解
cout<<"最大路径和为："<<maxAdd[0][0]<<endl;
cout<<"路径为："<<endl;
int k=0;
for(int i=0;i<n;i++){
cout<<t[i][k]<<" ";
k=path[i][k];
}
return maxAdd[0][0];
}
最长子串和
问题
给定一个整数序列（可能含负数），求出子序列形如\(\sum_{k=i}^j a_k\)，使得子序列中的元素和最大
分析
- 考虑初始子问题，当序列只有一个元素时，最大子序列和为该元素
- 考虑叠加子问题，当之前序列的最大子序列和为负数时，最大子序列和为当前元素，否则为之前序列的最大子序列和加上当前元素\[f(i)=\max\{f(i-1)+a_i,a_i\} \]
实现
int maxSubSum(int a[], int n){
int maxSum = 0;
int sIndex = 0;
int eIndex = 0;
for(int i = 0; i < n; i++){
int thisSum = 0;
for(int j = i; j < n; j++){
thisSum += a[j];
if(thisSum > maxSum){
maxSum = thisSum;
sIndex = i;
eIndex = j;
}
}
}
for(int i = sIndex; i <= eIndex; i++){
cout << a[i] << " ";
}
return maxSum;
}
练习
-
- 题目：Ackerman函数的递归定义为\[A(m,n)=\begin{cases} n+1, & m=0\\ A(m-1,1), & m>0,n=0\\ A(m-1,A(m,n-1)), & m>0,n>0 \end{cases} \]请用动态规划的方法求解Ackerman函数的值。
- 实现
int ackerman(int m, int n){ int dp[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0) dp[i][j]=j+1; else if(j==0) dp[i][j]=dp[i-1][1]; else dp[i][j]=dp[i-1][dp[i][j-1]]; } } } -
- 问题：有面试为\((v_1,v_2,...v_n)\)的n种纸币，每种纸币的数量无限，现在要找给客户y元钱，使支付张数最少，求最少张数。
- 分析：设\(dp[i]\)为找零i元钱的最少张数，那么有\[dp[i]=\min\{dp[i-v_j]+1\} \]其中\(j=1,2,...,n\)，且\(dp[0]=0\)。
- 实现
int minCoin(int v[], int n, int y){ int dp[y+1]; dp[0]=0; for(int i=1;i<=y;i++){ dp[i]=INT_MAX; for(int j=0;j<n;j++){ if(i>=v[j]&&dp[i-v[j]]+1<dp[i]){ dp[i]=dp[i-v[j]]+1; } } } return dp[y];