动态规划初步笔记

本文为该书的笔记：刘汝佳. 算法竞赛入门经典.第2版[M]. 清华大学出版社, 2014.

动态规划是一种思想，一种手段，而不是算法。需要理解它的基本思路和特点。

学习目标

• 理解状态和状态转移方程
• 理解最优子结构和重叠子问题
• 熟练运用递推法和记忆化搜索求解数字三角形问题
• 熟悉 DAG上动态规划的常见思路、两种状态定义方法和刷表法
• 掌握记忆化搜索在实现方面的注意事项
• 掌握记忆化搜索和递推中输出方案的方法
• 掌握递推中滚动数组的使用方法
• 熟练解决经典动态规划问题

动态规划的理论性和实践性都比较强，一方面需要理解“状态”、“状态转移”、“最优子结构”、“重叠子问题”等概念，另一方面又需要根据题目的条件灵活设计算法。可以这样说，对动态规划的掌握情况在很大程度上能直接影响一个选手的分析和建模能力。

数字三角形问题

动态规划的思考：
当前位置 (i,j) –> 一个状态
状态 (i,j) 的指标函数 d(i,j) –> 从格子 (i,j) 出发能得到的最大和（包括格子 (i,j) 本身的值）
原问题的解 –> d(1,1)
包括格子 (i,j) 本身的值 –> a(i,j)
状态转移方程：

d(i,j)=a(i,j)+max(d(i+1,j)+d(i+1,j+1))

状态转移方程的计算：
1. 递归计算（相同的子问题被重复计算了多次）
2. 递推计算
关键：边界 和 计算顺序
时间复杂度： 状态总数×每个状态的决策个数×决策时间
3. 记忆化搜索

DAG上动态规划

DAG（有向无环图）

描述
有n个矩形，每个矩形可以用a,b来描述，表示长和宽。矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a < c,b < d或者b < c,a < d（相当于旋转X90度）。例如（1,5）可以嵌套在（6,2）内，但不能嵌套在（3,4）中。你的任务是选出尽可能多的矩形排成一行，使得除最后一个外，每一个矩形都可以嵌套在下一个矩形内。

输入
第一行是一个正整数N(0< N <10)，表示测试数据组数，
每组测试数据的第一行是一个正正数n，表示该组测试数据中含有矩形的个数(n <= 1000)
随后的n行，每行有两个数a,b(0 < a,b < 100)，表示矩形的长和宽

输出
每组测试数据都输出一个数，表示最多符合条件的矩形数目，每组输出占一行

样例输入 
1 
10 
1 2 
2 4 
5 8 
6 10 
7 9 
3 1 
5 8 
12 10 
9 7 
2 2

样例输出 
5

“可嵌套”是一个“二元关系”，所以可以用图来建模。
如下图所示：

矩形 X 可以嵌套到 Y 里面，则从 X 到 Y 连一条有向边。即

该题目为DAG上最长路径问题。
设 i 为图的一个节点，即为状态。
d(i) 即为状态的指标函数，表示从节点 i 出发的最长路的长度
状态转移方程为

d(i)=max{d(j)+1|(i,j)∈E}

E 为边集， (i,j)∈E 即

首先，使用邻接矩阵建立图

for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        if( (nodes[i].x<nodes[j].x && nodes[i].y<nodes[j].y) ||
           (nodes[i].x<nodes[j].y && nodes[i].y<nodes[j].x) ){
//            如果i矩形可以嵌套在j矩形里面（即i矩形小于j矩形），则 i->j
            G[i][j] = 1;
        }
    }
}

之后，使用记忆化搜索计算节点处的状态指标函数：

memset(d,0,sizeof(d));
for(int i=0;i<n;i++){
    dp(i);
}

int dp(int i){
    int& ans = d[i];
    if(ans > 0)
        return ans;
    ans = 1;
    for(int j=0;j<n;j++){
        if(G[i][j])
            ans = max(ans,dp(j)+1);
    }
    return ans;
}

最后，找到最长路长度：

cout << *max_element(d,d+MAXN);

完整程序：

#define LOCAL
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
//#include <stdio.h>
#include <cstdlib>
#include<time.h>
#include <ctype.h>
#include <sstream>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define MAXN 1002


using namespace std;

int n;
//保存图的邻接矩阵
int G[MAXN][MAXN];
int d[MAXN];

struct node{
//    边长
    int x,y;
};
struct node nodes[MAXN];

//计算i节点的深度
int dp(int i){
    int& ans = d[i];
    if(ans > 0)
        return ans;
    ans = 1;
    for(int j=0;j<n;j++){
        if(G[i][j])
            ans = max(ans,dp(j)+1);
    }
    return ans;
}


int main()
{
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // LOCAL
    int N;
    cin >> N;
    while(N--){
        memset(G,0,sizeof(G));
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> nodes[i].x;
            cin >> nodes[i].y;
        }
//        使用邻接矩阵保存图
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if( (nodes[i].x<nodes[j].x && nodes[i].y<nodes[j].y) ||
                   (nodes[i].x<nodes[j].y && nodes[i].y<nodes[j].x) ){
//                    如果i矩形可以嵌套在j矩形里面（即i矩形小于j矩形），则 i->j
                    G[i][j] = 1;
                }
            }
        }
        memset(d,0,sizeof(d));
        for(int i=0;i<n;i++){
            dp(i);
        }
        cout << *max_element(d,d+MAXN);

    }

  return 0;
}

如果需要以字典序输出最优解：

#define LOCAL
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
//#include <stdio.h>
#include <cstdlib>
#include<time.h>
#include <ctype.h>
#include <sstream>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define MAXN 1002
//int s[MAXN];
//int p[MAXN];
//char *s="`1234567890-=QWERTYUIIOP[]\\ASDFGHJKKL;'ZXCVBNM,./";

using namespace std;
// 因为各个结点的权值各不相同且都是正整数，直接用权值作为结点编号
const int maxn = 1000;
int n, m, c[maxn], topo[maxn], t;
//保存图的邻接矩阵
int G[MAXN][MAXN];
int d[MAXN];

struct node{
//    边长
    int x,y;
};
struct node nodes[MAXN];

//计算i节点的深度
int dp(int i){
    int& ans = d[i];
    if(ans > 0)
        return ans;
    ans = 1;
    for(int j=0;j<n;j++){
        if(G[i][j])
            ans = max(ans,dp(j)+1);
    }
    return ans;
}
//打印输出节点i出发的最长路经
void print_ans(int i){
    cout << nodes[i].x << " " << nodes[i].y << "\n";
    for(int j=0;j<n;j++){
        if(G[i][j] && d[i] == d[j]+1){
            print_ans(j);
            break;
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // LOCAL
    int N;
    cin >> N;
    while(N--){
        memset(G,0,sizeof(G));
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> nodes[i].x;
            cin >> nodes[i].y;
        }
//        使用邻接矩阵保存图
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if( (nodes[i].x<nodes[j].x && nodes[i].y<nodes[j].y) ||
                   (nodes[i].x<nodes[j].y && nodes[i].y<nodes[j].x) ){
//                    如果i矩形可以嵌套在j矩形里面，则 i->j
                    G[i][j] = 1;
                }
            }
        }
        memset(d,0,sizeof(d));
        for(int i=0;i<n;i++){
            dp(i);
        }
//        cout << *max_element(d,d+MAXN) << "\n";
        int ii=distance(d,max_element(d,d+MAXN));
//        cout << ii << "\n";
        print_ans(ii);

    }



  return 0;
}

硬币问题（固定终点的最长路和最短路问题）

有n种硬币，面值分别为V1，V2，V3，,,VN每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？ 输出硬币数目的最小值和最大值

样例：

1 
1025
7

3
2
5
7
11
13
17

输出：

61
512

d(i) 的含义：“从节点 i 出发到节点 0 的最长路径长度”
和矩形嵌套问题不一样的是：节点S不一定能够达到0.
这个题目需要一边构建图一边求最值。

记忆化搜索方法完整程序：

#define LOCAL
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
//#include <stdio.h>
#include <cstdlib>
#include<time.h>
#include <ctype.h>
#include <sstream>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define MAXN 3002
//int s[MAXN];
//int p[MAXN];
//char *s="`1234567890-=QWERTYUIIOP[]\\ASDFGHJKKL;'ZXCVBNM,./";

using namespace std;

const int INF = 1 << 30;
int n;


struct node{
//    边长
    int x,y;
};
struct node nodes[MAXN];
int dmin[MAXN],dmax[MAXN];
//硬币种类
int V[MAXN];
int S;
//计算i节点的深度

int dpmin(int SS){
    int& ans = dmin[SS];
    if(ans != -1)
        return ans;
    ans = INF;
    for(int i=0;i<n;i++){
        if(SS >= V[i]){
            ans = min(ans,1+dpmin(SS-V[i]));
        }
    }
    return ans;
}
int dpmax(int SS){
    int& ans = dmax[SS];
    if(ans != -1)
        return ans;
    ans = -INF;
    for(int i=0;i<n;i++){
        if(SS >= V[i]){
            ans = max(ans,1+dpmax(SS-V[i]));
        }
    }
    return ans;
}


int main()
{
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // LOCAL

    int N;
    cin >> N;
    while(N--){
        cin >> S;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> V[i];
        }
        memset(dmin,-1,sizeof(dmin));
        memset(dmax,-1,sizeof(dmax));
        dmin[0]=dmax[0]=0;
        cout << dpmin(S) << endl;
        cout << dpmax(S) << endl;

    }
  return 0;
}

递推方法完整程序:

#define LOCAL
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
//#include <stdio.h>
#include <cstdlib>
#include<time.h>
#include <ctype.h>
#include <sstream>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define MAXN 3002

using namespace std;
const int INF = 1 << 30;
int n;

struct node nodes[MAXN];
int dmin[MAXN],dmax[MAXN];
//硬币种类
int V[MAXN];
int S;


int main()
{
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // LOCAL

    int N;
    cin >> N;
    while(N--){
        cin >> S;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> V[i];
        }
        dmin[0]=dmax[0]=0;
        for(int i=1;i<=S;i++){
            dmin[i]=INF;
            dmax[i]=-INF;
        }
        for(int i=1;i<=S;i++){
            for(int j=0;j<n;j++){
                if(i>=V[j]){
                    dmin[i]=min(dmin[i],dmin[i-V[j]]+1);
                    dmax[i]=max(dmax[i],dmax[i-V[j]]+1);
                }
            }
        }

        cout << dmin[S] << endl;
        cout << dmax[S] << endl;
    }
  return 0;
}

若需要以字典序打印输出：

void print_ans(int* d,int S){
    for(int i=1;i<=n;i++){
        if(S>=V[i] && d[S]==d[S-V[i]]+1){
            cout << V[i] << " ";
            print_ans(d,S-V[i]);
            break;
        }
    }
}

以字典序打印（空间换时间）：
完整程序：

#define LOCAL
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
//#include <stdio.h>
#include <cstdlib>
#include<time.h>
#include <ctype.h>
#include <sstream>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define MAXN 3002
//int s[MAXN];
//int p[MAXN];
//char *s="`1234567890-=QWERTYUIIOP[]\\ASDFGHJKKL;'ZXCVBNM,./";

using namespace std;

const int INF = 1 << 30;
int n, m, c[maxn], topo[maxn], t;
//保存图的邻接矩阵
int G[MAXN][MAXN];
int d[MAXN];

int dmin[MAXN],dmax[MAXN];
//硬币种类
int V[MAXN];
int S;

int min_coin[MAXN],max_coin[MAXN];
void print_ans1(int* d,int S){
    if(S){//此时d[S]可以是0
        cout << V[d[S]] << " ";
        print_ans1(d,S-V[d[S]]);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    #endif // LOCAL

    int N;
    cin >> N;
    while(N--){
        cin >> S;

        cin >> n;
        for(int i=0;i<n;i++){
            cin >> V[i];
        }
        dmin[0]=dmax[0]=0;
        for(int i=1;i<=S;i++){
            dmin[i]=INF;
            dmax[i]=-INF;
        }
        for(int i=1;i<=S;i++){
            for(int j=0;j<n;j++){
                if(i>=V[j]){
                    if(dmin[i]>dmin[i-V[j]]+1){
                        dmin[i]=dmin[i-V[j]]+1;
                        min_coin[i]=j;
                    }
                    if(dmax[i]<dmax[i-V[j]]+1){
                        dmax[i]=dmax[i-V[j]]+1;
                        max_coin[i]=j;
                    }
                }
            }
        }

        print_ans1(min_coin,S);
        cout << "\n";
        print_ans1(max_coin,S);


    }
  return 0;
}

小结：

1. DAG 上最长路和最短路可以用记忆化搜索和递推两种方法实现。
   记忆化搜索可以使用特殊值表示还没算过，也可以使用另外一个数组表示这个状态。
   递推的方法不需要考虑是否算过。
2. 打印解的时候既可以根据 d 值（即状态的指标值）重新计算出每一步的最优决策，也可以在动态规划的时候“顺便”记录下每步的最优决策。
3. DAG 上最长路（最短路）有两种对称的状态定义方式。
   状态1：设 d(i) 为从 i 出发的最长路，则d(i)=max{d(j)+1|(i,j)∈E}
   状态2：设 d(i) 为从 i 出发的最长路，则d(i)=max{d(j)+1|(i,j)∈E}
   如果使用状态2，“硬币问题”和“矩形嵌套”问题在表达方式上就是一样的了。都是： d(i) 为以 i `为结束的最长路。则硬币问题也可以使用先使用邻接矩阵建图再从 0 处使用记忆化搜索的方式处理。
   对于样例：

1
10
2

3
5

其图可建立为：

4. 在使用状态 2 时可能会遇到一个问题：状态转移方程可能不好计算（可能不好反着枚举(j,i)）。
这时需要使用“刷表法”。
传统的递推方法（填表法）可以表示成“对于每个状态 i ,计算 f(i) ”,这需要对于每个状态 i ，找到 f(i) 依赖的所有状态。
“刷表法”是对于每个状态 i ，更新 f(i) 所影响到的状态。
对应到 DAG 上最长路的问题，就相当于按照拓扑序枚举 i ，对于每个 i ，枚举边 (i,j) ,然后更新 d[j]=max(d[j],d[i]+1) 。即如上图中从 10 的状态更新 5 和 7 的状态，所有节点的状态都更新一遍之后方才得到节点的指标函数值。（只有当每个状态所依赖的状态对它的）