动态规划

ゞ浴缸里的玫瑰 2022-05-25 09:44 446阅读 0赞

## 基本思想： ##

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

## 区别： ##

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

## 分类： ##

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。  
举例：  
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；  
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；  
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；  
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等；  
应用实例：  
最短路径问题 ，项目管理，网络流优化等；  
POJ动态规划题目列表：  
容易：  
　　1018,1050,1083,1088,1125,1143,1157,1163,1178,1179,1189,1191,1208,1276,1322,1414,1456,1458,1609,1644,1664,1690,1699,1740,1742,1887,1926,1936,1952,1953,1958,1959,1962,1975,1989,2018,2029,2039,2063,2081,2082,2181,2184,2192,2231,2279,2329,2336,2346,2353,2355,2356,2385,2392,2424。  
不易：  
　　1019,1037,1080,1112,1141,1170,1192,1239,1655,1695,1707,1733(区间减法加并查集),1737,1837,1850,1920(加强版汉罗塔),1934(全部最长公共子序列),1964(最大矩形面积，O(n\*m)算法),2138,2151,2161,2178。  
推荐：

1015,1635,1636,1671,1682,1692,1704,1717,1722,1726,1732,1770,1821,1853,1949,2019,2127,2176,2228,2287,2342,2374,2378,2384,2411。

## 基本模型： ##

根据上例分析和动态规划的基本概念，可以得到动态规划的基本模型如下：

(1)确定问题的决策对象。 (2)对决策过程划分阶段。 (3)对各阶段确定状态变量。 (4)根据状态变量确定费用函数和目标函数。 (5)建立各阶段状态变量的转移过程，确定状态转移方程。

## 状态转移方程的一般形式： ##

一般形式： U：状态； X：策略  
　　顺推：f\[Uk\]=opt\{f\[Uk-1\]+L\[Uk-1,Xk-1\]\} 其中， L\[Uk-1,Xk-1\]： 状态Uk-1通过策略Xk-1到达状态Uk 的费用 初始f\[U1\]；结果：f\[Un\]。  
倒推：  
　　f\[Uk\]=opt\{f\[Uk+1\]+L\[Uk,Xk\]\}  
　　L\[Uk,Xk\]： 状态Uk通过策略Xk到达状态Uk+1 的费用  
　　初始f\[Un\]；结果：f(U1)

## 适用条件： ##

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

1.**最优化原理**（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，**一个最优化策略的子策略总是最优的**。一个问题满足最优化原理又称其具有最优子结构性质。

2.**无后效性**将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，**它以前各阶段的状态无法直接影响它未来的决策**，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

3.子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。**动态规划实质**上是一种**以空间换时间的技术**，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

## **动态规划思想设计的算法：** ##

从整体上来看基本都是**按照得出的递推关系式进行递推**。

动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的。

## 通过两种思路来实现： ##

1.一种是递推结果仅使用Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过复制覆盖到Data1之上，如此反复，即可推得最终结果。这种做法有一个局限性，就是对于递推与前面若干阶段相关的问题，这种做法就比较麻烦；而且，每递推一级，就需要复制很多的内容，与前面多个阶段相关的问题影响更大。

2.另外一种实现方法是，对于一个可能与前N个阶段相关的问题，建立数组Data\[0..N\]，其中各项为前面N个阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少，速度几乎不受影响，而且需要保留不同的阶段数也都能很容易实现。

当采用以上方法仍无法解决内存问题时，也可以采用对内存的动态申请来使绝大多数情况能有效出解。而且，使用动态内存还有一点好处，就是在重复使用内存而进行交换时，可以只对指针进行交换，而不复制数据，这在实践中也是十分有效的。

###     ###

应用：

### 作用 ###

在编程中常用解决最长公共子序列问题、 [矩阵][Link 1]连乘问题、凸多边形最优三角剖分问题、电路布线等问题。

### 搜索 ###

记忆化

给你一个数字三角形, 形式如下:

2 3

4 5 6

7 8 9 10

找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.

无论对于新手还是老手，这都是再熟悉不过的题了，很容易地，我们 *写出状态转移方程：*

f\[i\]\[j\]=a\[i\]\[j\] + min\{f\[i+1\]\[j\]，f\[i+1\]\[j+1\]\}(a\[i\]\[j\]表示当前状态,f\[i\]\[j\]表示指标函数)

对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么简单了。

*解决方法：*

我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的 *递归函数*:

int f(int i, int j, int (*a)[4])
    {
        int f1, f2, tmp=0, k;
        if(i==0||j==0)
        return a[0][0];
        if(j==i)
        {
            for(k=0;k<=i;k++)
            tmp+=a[k][k];
            return tmp;
        }
        f1=f(i-1, j, a);
        f2=f(i-1, j-1, a);
        if(f1<f2)
            return f2+a[i][j];
        else
            return f1+a[i][j];
    }

显而易见，这个算法就是最简单的搜索算法。时间复杂度为2^n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组： *Opt\[i, j\] - 每产生一个f(i, j)，将f(i, j)的值放入opt中，以后再次调用到f(i, j)的时候，直接从opt\[i, j\]来取就可以了。*于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下， [递归算法][Link 2]能更好地避免浪费，在比赛中是非常实用的。

并且记忆搜索占的内存相对来说较少。

计算核心片段：

for(inti=n-1;i>=1;--i)//从倒数第二行开始
    {
        for(intj=1;j<=i;j++)
        {
            if(a[i+1][j][1]>a[i+1][j+1][1])//左边大
        {
            a[i][j][2]=0;//选择左边
            a[i][j][1]+=a[i+1][j][1];
        }
        else//右边大
        {
            a[i][j][2]=1;//选择右边
            a[i][j][1]+=a[i+1][j+1][1];
        }

练习题

USACO2.2 Subset Sums

题目如下：

对于从1到N的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。

举个例子，如果N=3，对于\{1，2，3\}能划分成两个子集合，他们每个的所有数字和是相等的：

\{3\}and \{1,2\}

这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果N=7，有四种方法能划分集合\{1，2，3，4，5，6，7\}，每一种分发的子集合各数字和是相等的:

\{1,6,7\} and \{2,3,4,5\} \{注 1+6+7=2+3+4+5\}

\{2,5,7\} and \{1,3,4,6\}

\{3,4,7\} and \{1,2,5,6\}

\{1,2,4,7\} and \{3,5,6\}

给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。

PROGRAM NAME: subset

INPUT FORMAT

输入文件只有一行，且只有一个整数N

SAMPLE INPUT (file subset . in)

OUTPUT FORMAT

输出划分方案总数，如果不存在则输出0。

SAMPLE OUTPUT (file subset.out)

参考程序如下（C++语言）：

#include<fstream>
    usingnamespacestd;
    constunsignedintMAX_SUM=1024;
    intn;
    unsignedlonglongintdyn[MAX_SUM];
    ifstreamfin("subset.in");
    ofstreamfout("subset.out");
    int main(){
        fin>>n;
        fin.close();
        ints=n*(n+1);
        if(s%4){
            fout<<0<<endl;
            fout.close();
            return0;
        }
        s/=4;
        inti,j;
        dyn[0]=1;
        for(i=1;i<=n;i++)
            for(j=s;j>=i;j--)
                if(j-i>0){
                    dyn[j]+=dyn[j-i];
                }
            fout<<(dyn[s]/2)<<endl;
            fout.close();
            return0;
        }
    USACO2.3LongestPrefix

题目如下：

在 [生物学][Link 3]中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。

如果一个集合 P 中的元素可以通过并运算（允许重复；并，即∪，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。并不是所有的元素都必须出现。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：

\{A, AB, BA, CA, BBC\}

序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。

PROGRAM NAME: prefix

INPUT FORMAT

输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。 [换行符][Link 4]并不是序列 S 的一部分。

SAMPLE INPUT (file prefix. in)

A AB BA CA BBC

ABABACABAABC

OUTPUT FORMAT

只有一行，输出一个整数，表示 S 能够分解成 P 中元素的最长前缀的长度。

SAMPLE OUTPUT (file prefix.out)

示例程序如下：

#include <stdio.h>
    #define MAXP 200
    #define MAXL 10
    char prim[MAXP+1][MAXL+1];
    int nump;
    int start[200001];
    char data[200000];
    int ndata;
    int main(int argc, char **argv)
    {
    FILE *fout, *fin;
    int best;
    int lv,lv2, lv3;
    if ((fin = fopen("prim. in", "r")) == NULL)
    {
    perror ("fopen fin");
    exit(1);
    }
    if((fout = fopen("prim.out", "w")) == NULL)
    {
    perror ("fopen fout");
    exit(1);
    }
    while (1)
    {
    fscanf (fin, "%s", prim[nump]);
    if (prim[nump][0] != '.')
    nump++;
    else
    break;
    }
    ndata = 0;
    while (fscanf (fin, "%s", data+ndata) == 1)
    ndata += strlen(data+ndata);
    start[0] = 1;
    best = 0;
    for (lv = 0; lv < ndata; lv++)
    if (start[lv])
    {
    best = lv;
    for (lv2 = 0; lv2 < nump; lv2++)
    {
    for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] == data[lv+lv3]; lv3++)
    if (!prim[lv2][lv3])
    start[lv + lv3] = 1;
    }
    }
    if (start[ndata])
    best = ndata;
    fprintf (fout, "%i\n", best);
    return 0;
    }

动态规划作为一种重要的信息学竞赛算法，具有很强的灵活性。以上提供的是一些入门练习题，深入的学习还需要逐步积累经验。

解决0-1背包问题时使用动态规划的实现（c++）

#include <stdio.h>
    typedef struct Object{
    int weight;
    int value; // float rate;
    }
    Object;
    Object * array; //用来存储物体信息的数组
    int num; //物体的个数
    int container; //背包的容量
    int ** dynamic_table; //存储动态规划表
    bool * used_table; //存储物品的使用情况
    //ouput the table of dynamic programming, it's for detection
    void print_dynamic_table(){
    printf("动态规划表如下所示:\n");
    /* for(int j=0; j<=container; j++) printf("%d ",j); printf("\n");*/
    for(int i=1; i<=num; i++) {
    for(int j=0; j<=container; j++)
    printf("%d ",dynamic_table[i][j]);
    printf("\n");
    }
    }
    //打印动态规划表
    void print_array(){
    for(int i=1; i<=num; i++)
    printf("第%d个物品的重量和权重:%d %d\n",i,array[i].weight,array[i].value);
    }
    //打印输入的物品情况//插入排序，按rate=value/weight由小到大排//动态规划考虑了所有情况，所以可以不用排序
    /*void sort_by_rate(){
    for(int i=2; i<=num; i++) {
    Object temp=array[i];
    for(int j=i-1; j>=1; j--)
    if(array[j].rate>temp.rate)
    array[j+1]=array[j];
    else break;
    array[j+1]=temp;
    }}*/
    void print_used_object(){
    printf("所使用的物品如下所示:\n");
    for(int i=1; i<=num; i++)
    if(used_table[i]==1)
    printf("%d-%d\n", array[i].weight, array[i].value);
    }
    //打印物品的使用情况
    /* 做测试时使用
    void print_used_table(bool * used_table){
    printf("used table as follows:\n");
    for(int i=1; i<=num; i++)
    printf("object %d is %d", i, used_table[i]);
    }*/
    void init_problem(){
    printf("输入背包的容量:\n");
    scanf("%d", &container);
    printf("输入物品的个数:\n");
    scanf("%d", &num);
    array=new Object[num+1];
    printf("输入物品的重量和价值, 格式如：4-15\n");
    for(int i=1; i<=num; i++) {
    char c;
    scanf("%d%c%d", &array[i].weight, &c, &array[i].value);
    // array[i].rate=array[i].value/array[i].weight;
    }
    print_array();
    }
    //对物体的使用情况进行回查
    void trace_back(){
    int weight=container;
    used_table=new bool[num+1];
    for(int i=1; i<=num; i++) used_table[i]=0;
    //initalize the used_table to be non-used
    for(int j=1; j<num; j++) {
    //说明物品j被使用
    if(dynamic_table[j][weight]!=dynamic_table[j+1][weight]) {
    weight-=array[j].weight;
    used_table[j]=1;
    }
    // print_used_table(used_table);
    }
    //检测第num个物品是否被使用
    if(weight>=array[num].weight)
    used_table[num]=1;
    }
    void dynamic_programming(){
    dynamic_table=new int * [num+1];
    for(int k=1; k<=num; k++)
    dynamic_table[k]=new int[container+1];
    //dynamic_programming table
    //为二维动态规划表分配内存
    for(int m=1; m<num; m++)
    for(int n=0; n<=container; n++)
    dynamic_table[m][n]=0;
    int temp_weight=array[num].weight;
    for(int i=0; i<=container; i++)
    dynamic_table[num][i]=i<temp_weight?0:array[num].value;
    //初始化动态规划表
    for(int j=num-1; j>=1; j--) {
    temp_weight=array[j].weight;
    int temp_value=array[j].value;
    for(int k=0; k<=container; k++)
    if(k>=temp_weight && dynamic_table[j+1][k] < dynamic_table[j+1][k-temp_weight]+temp_value)
    dynamic_table[j][k]=dynamic_table[j+1][k-temp_weight]+temp_value;
    else dynamic_table[j][k]=dynamic_table[j+1][k];
    }//构建动态规划表
    print_dynamic_table();//打印动态规划表
    }
    void main(){
    init_problem();
    dynamic_programming();
    trace_back();
    print_used_object();
    }

**0009算法笔记——【动态规划】动态规划与斐波那契数列问题,最短路径问题：**

**https://blog.csdn.net/liufeng\_king/article/details/8490770**

**POJ 动态规划题目列表**

**http://www.cnblogs.com/qijinbiao/archive/2011/09/02/2163460.html**

[Link 1]: https://baike.baidu.com/item/%E7%9F%A9%E9%98%B5
[Link 2]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95
[Link 3]: https://baike.baidu.com/item/%E7%94%9F%E7%89%A9%E5%AD%A6
[Link 4]: https://baike.baidu.com/item/%E6%8D%A2%E8%A1%8C%E7%AC%A6