动态规划不是一种特定算法，而是一种解决问题的思路，有些问题可以分成几个阶段，每个阶段做出特定的决策可以使整个问题得到最优解。

        动态规划与贪心不一样的地方是，贪心算法不依赖子问题，只对下一个阶段或子问题进行决策，因此很多情况下得不到最优解，而动态规划依赖于每个子问题的解，从而可以得到整个问题的最优解。因此动态规划一般使用自底向上的方法进行求解。

        并不是所有题都可以使用动态规划进行解决，能采用该方式的题必须具备以下两个条件：一是具有最优性原理，最优性原理的意思是一个问题的最优解只取决于其子问题的最优解，就是说所有子问题的最优解相加就是整个问题的最优解。二是无后效性，意思就是未来做出的决策不会影响到前面的结果。比如说一条固定的道路，那么不管以后如何走都不影响前面走过的路径，就是无后效性，如果说道路不固定，往后走会改变之前已经走过的路，那么就不具有无后效性。

例题：求下图从A到E的最短路径：

image.png

        从图上可知，整个路径是分成4个阶段（A-B，B-C，C-D，D-E），每个阶段走哪条路并不影响之前的结果，因此改题是无后效性，另外，每个阶段的最短路径相加就是整个问题的最短路径，因此也具有最优性原理，可以使用动态规划，并采用自底向上的方式求解，因此从终点E开始进行推算：

第一阶段S1，从D到E：

    S1(D1)=3 S1(D2)=4 S1(D3)=3

第二阶段S2，从C到D：

    S2(C1)=MIN([C1-D1]+S1(D1), [C1-D2]+S1(D2)) = MIN(8,10)=8

    S2(C2)=[C2-D1]+S1(D2)=8

    S2(C3)=[C3-D3]+S1(D3)=11

    S2(C4)=[C4-D3]+S1(D3)=6

第三阶段S3，从B到C：

    S3(B1)=MIN([B1-C1]+S2(C1), [B1-C2]+S2(C2), [B1-C3]+S2(C3))=MIN(9,14,14)=9

    S3(B2)=MIN([B2-C2]+S2(C2), [B2-C4]+S2(C4))=MIN(16,10)=10

第四阶段S4，从A到B：

    S4(A)=MIN([A-B1]+S3(B1), [A-B2]+S3(B2))=MIN(14,13)=13

因此A到E的最短路径为13（A-B2-C4-D3-E）


动态规划也可以自顶向下进行，因此上题也可以如下接：

第一阶段：

    B1 最短路径：5

    B2 最短路径：3

第二阶段：

    C1 最短路径：5+1=6

    C2 最短路径：MIN（B1+B1C2,B2+B2C2)=MIN(11,11)=11

    C3 最短路径：5+3=8

    C4 最短路径：3+4=7

第三阶段：

    D1 最短路径：MIN(C1+C1D1,C2+C2D1)=MIN(11, 16)=11

    D2 最短路径：C1+6=12

    D3 最短路径：MIN(C3+C3D3,C4+C4D3)=MIN(16,10)=10

第四阶段：

    E 最短路径：MIN(D1+D1E,D2+D2E,D3+D3E)=MIN(14, 16, 13)=13

最大升序列

如下方的序列，求最大的升序列  

32，2，56，3，65，4，76，23，12，54，12，43，12，57，13，54，13，23，11，89，22，12，67，43，56

        使用动态规划的方法来解体，从后面思考，最后一个数为56，他的最大升序列为1。再从上一个数思考，43小于56，则最大升序列是56的最大升序列基础上再加1，也就是2。继续往前一个数思考，67比43大，且他后面没有比他大的数了，因此他的最大升序列从1开始，继续往前，12，他后面有3个数都比他大，因此他的最大子序列是后面三个数最大序列的最大值+1，也就是43的最大升序列2+1=3，如此进行反推，则可以求得最大升序列。

image.png

#include <iostream>
using namespace std;

int arr[25] ={32,2,56,3,65,4,76,23,12,54,12,43,12,57,13,54,13,23,11,89,22,12,67,43,56};
int flag[25] = {0}; //记录最大序列

//找后续数值大于等于val并且序列最大的
int GetMaxNum(int start, int val) {
    int tmp = 1;
    for (int i = start+1; i < 25; i++)
    {
        if (arr[i] >= val && flag[i] >= tmp) 
            tmp = flag[i]+1; //该数的最大序列是最大的+1
    }
    return tmp;
}

int main(){
    int max = 1;
    for (int i = 24; i > -1; i--)
    {
        //从后往前逐个处理
        flag[i] = GetMaxNum(i, arr[i]);
        if (flag[i] > max)
        {
            max = flag[i]; //记录最大序列数
        }
    }
    cout << max << endl;
    //打印其中一个最大升序列
    int tmp = -1;
    for (int i = 0; i < 25; i++)
    {
        if (flag[i] == max && arr[i] >= tmp) //序列数相等且升序
        {
            cout << arr[i] << " ";
            max--;
            tmp = arr[i];    
        }
    }
    return 0;
}
//输出结果
11
2 3 4 12 12 12 13 13 23 43 56

        这题也可以使用正推的方法，结果的步骤其实是一样的，正推的时候，当前最大序列是先择比当前数小的数的最大序列+1。

最长子序列

如下2个序列，求其最大子序列。

序列一：2，4，5，4，7，8，2，1

序列二：4，3，6，5，7，9，2，2

从下图可以看到他们的最大子序列为：3，5，7，2

image.png

        分析：这个序列的最长子序列只跟序列长度有关，因此可以使用动态规划来解，反推的大致思路如下：如果序列一和序列二的最后一位相等，则它们的最大子序列为：序列一减最后一位和序列二减最后一位的最大子序列+1， 如果最后一位不相等（例子中就是不相等的情况），则它们的最大子序列是 MAX( 序列一减最后一位和序列二的最大子序列， 序列二减最后一位和序列一的最大子序列)，求大的那一个。

        因此这题可以使用递归的方式来解，一般动态规划会使用标记法（备忘录）来记录之前的记过，因此如果使用MS[i][j] 数组来记录 长度为i，j的序列一和序列二数组的最大子序列。则有如下的判断:

if (s1[i] == s2[i])  //最后一位相等
    ms[i][j] = ms[i-1][j-1]+1   // 则是之前的最大值+1
else
    ms[i][j] = MAX(ms[i-1][j], ms[i][j-1]) //两个最大序列中较大的一个

递归代码：（也是动态规划的思想）

#include <iostream>
#include <string>
using namespace std;

int MaxSubString(string s1, string s2){

    int len1 = s1.length();
    int len2 = s2.length();

    if (len1==0 || len2==0)
        return 0;
    
    if (s1[len1-1] == s2[len2-1])
        return MaxSubString(s1.substr(0, len1-1), s2.substr(0, len2-1)) + 1;
    else
        return max(MaxSubString(s1, s2.substr(0, len2-1)), MaxSubString(s1.substr(0, len1-1), s2));
}

int main(){
    string s1 = "24547821";
    string s2 = "43657922";
    cout << MaxSubString(s1,s2) << endl;
}
//输出
4

备忘录代码：所谓备忘录，就是把中间的值记录下来，跟搜索的打标记类似，这样就可以使用之前的值而不需要每次都重新计算

#include <iostream>
#include <string>
using namespace std;

int main(){
    string s1 = "24547821";
    string s2 = "43657922";

    int ms[9][9] = {0}; //使用1-8位记录

    for (int i = 1; i < 9; i++){
        for (int j = 1; j < 9; j++)
        {
            //比较第N位（数组下标需要-1，从而解决从下标开始负数问题）
            if (s1[i-1] == s2[j-1])
                ms[i][j] = ms[i-1][j-1]+1;
            else
                ms[i][j] = max(ms[i][j-1], ms[i-1][j]);
        }
    }
    cout << ms[8][8] << endl;
}
//输出
4

设备分配

        题目：把N台设备分配给M家公司，并给出每家公司获得K台设备的收益表格，使得总利益最大化，求最大的总利益。 例：4台设备分配给三家公司，每家公司获得K台设备的收益由以下表格给出：

公司/收益1台2台3台4台
公司一20304050
公司二10 20 3060
公司三30405050

        分析：用一个Value[][]数组来记录表中的数据，再使用一个备忘录 mx[i][j] 来记录 i 家公司分配 j 台设备的最大利益，则：

i 家公司分配 j 台设备的最大利益为： i-1 家公司分配 k (0-j) 台设备设备 + 第 i 家公司分配 j-k 台设备的最大值，后一个变量 i 家公司分配 j-k 台电脑是个定值，可以在Value表格里查找，因此可以用循环表示：

    int max = 0;
    //需要循环来确定前I-1家公司分别分配k（0-j）台设备，哪个情况能得到最大值
    for (int k = 0; k <=j; k++)  
    {
        //收益 = 前I-1家公司分配k台设备的最大值 + 第i家公司分配j-k
        int val = mx[i-1][k] + Value[i][j-k]; 
        if (val > max)  //更新最大收益
            max = val;
    }
    mx[i][j] = max; // i家公司分配j台设备的最大收益

        从上述代码可知，需要求得 N家公司分配M个设备的最大收益，必须要先算出mx[i-1][k]的所有值，如果是4台设备3家公司，则需要知道2家公司0台设备的最大值（mx[2][0]）,2家公司1台设备的最大值（mx[2][1]）,2家公司2台设备的最大值（mx[2][2]）,2家公司3台设备的最大值（mx[2][3]）,也就是所有 i （1，N）家公司 j （1，M）台设备的最大值。因此代码如下：

#include <iostream>
using namespace std;

int Value[4][5] = {{0,0,0,0},{0,20,30,40,50},{0,10,20,30,60},{0,30,40,50,50}};
int mx[4][5] = {0};

int N = 3;
int M = 4;

int main(){
    
    //公司从1开始，便于表达
    for (int i = 1; i <= 3; i++)
    {
        for (int j = 0; j <= 4; j++) //设备可以从0台开始分
        {
            int max = 0;
            for (int k = 0; k < j; k++) //第I家公司尝试分配0-J台设备，获取最大收益
            {
                int val = mx[i-1][k] + Value[i][j-k];
                if (val > max) // 更新最大收益
                    max = val;
            }
            mx[i][j] = max; //记录I家公司分J台设备的最大收益
        }
    }
    
    cout << mx[3][4] << endl;
    return 0;
}
//输出
70

        这一题可以转换为0/1背包问题求解，会更加简化。

显示更多
Copyright © 2018-2023 lazypos.cn