vlambda博客
学习文章列表

引入

碰动态规划问题摸不着头脑？总结不出动态规划的类型？那么看完此篇文章，就能一脚迈进动态规划的大门。

我们在用递归求解问题的过程中，可能会存在将递归的某一环节计算多次的现象，因为之前的递归结果无法有效存储，下次碰到一样的值还需要重新计算一次，下面引出一个例子：

相信大家都知道斐波那契数列，那我们由斐波那契数列递归求解过程中带来的问题来引出动态规划问题。

斐波那契数列的规律为：当n > 2时，fib(n)=fib(n-1)+fib(n-2),当n为1或2时，fib(n)=1。假如我们让电脑代入这个递归式来求fib(5)，则求解过程如下图：

我们可以看到，如果我们按照如上的递归式来求一个斐波那契数，那么当n很大时，这棵树会非常庞大，且从中我们也可看出，电脑会非常傻的把fib(3)算了两遍，这种问题叫做重叠子问题，所以这个算法的时间复杂度会达到O(2^n),但实际上我们没有必要把fib(3)算两遍，我们在算第一遍时把它保存起来，在下次需要时直接调用就可以了。

因此我们在计算fib(5)时，完全可以从fib(1)开始计算，从1一直算到5，并不断保存，在必要时调用之前保存的值，而不需要重新运算，这样算法的时间复杂度瞬间就降到O(n)了。

所以我们在做动态规划时，首先要用到的就是这个思想，可以看出，动态规划的特点之一就是开辟内存保存数值，那么我们可以根据开辟内存的方式分为一维动态规划问题和二维动态规划问题，下面我们来具体介绍。

第一类问题（一维）

1.求薪水问题

我们来看下面的图，从上到下依次为8种工作，横轴代表工作所占的时间段，红色字体代表每份工作的薪水，两份同一时间的工作不能同时做，我们求的问题是一个员工怎样在0到11的时间段内获取最大的薪水。

我们首先思考这道题的本质，就是选不重合的工作，求能最多得到的薪水，我们先建立一个数组workvalue来保存每份工作的薪水。

我们先按照开辟内存的思想来做这道题，之后我会说明为什么要开辟内存。由上文的动态规划规律可知，我们可以依次从只做前一个工作能得到的最大薪水、只做前二个工作能得到的最大薪水、只做前三个工作能得到的最大薪水来思考，并建立一个value数组来保存它们，假如我们想求前6个工作中选哪些工作才能赚的最多，那么我们可以有两个选择：做或者不做这份工作，第一种，假如我们选择第6份工作，我们先找到最近的一个与第6份工作时间不重合的工作（第2份工作），那最大薪水为做第6份工作得到的钱加上做前2个工作能得到的最大的薪水（本题就是第6份工作的薪水3+value[2]）；第二种，我们可以选择不做第6份工作，那么最大的薪水就是做前5个工作得到的最大的薪水。因此：

value[6]=max(3+value[2],value[5]);

我们可以看出，如果我们不开辟数组，用递归的思想接着求value[2]，那么不可避免地计算了重复子问题，因此我们选择开辟数组，从前往后用动态规划的思想做。此外，我们还应设立pre数组来存每个工作的前一个与之不重合的工作，例如pre[6]=2。因此我们可以写出如下代码来解决上述问题：

#include <iostream>
using namespace std;
int value[10];
int workvalue[8] = {5, 1, 8, 4, 6, 3, 2, 4};
int pre[8] = {0, 0, 0, 1, 0, 2, 3, 5};
int main() {
  value[0] = 0;
  value[1] = 5;
  value[2] = 5;
  for (int i = 3; i <= 8; i++) {
    value[i] = max(value[i - 1], value[pre[i - 1]] + workvalue[i - 1]);
  }
  cout << value[8];
  return 0;
}

求出结果等于13，即最多的薪水。那么这道问题解决，鉴于如果此题换个衣服大家可能会不认识的现象，我们接下来再搞一道同类型不同描述的问题。

2.求最大数

我们可以在如下arr数组中的数字中可以任意选数字，但是不能选相邻的数字，输出我们选的数字中和最大的值。

我们可以一眼看出，此题同样是个选择与否的问题，不能选相邻的数就如求薪水问题中的不能同时做两份工作，我们先来试试递归，用递归从后往前来做，我们设opt（n）是前n个数中选择的数相加最大的值，那么当我们考虑opt(n)时，我们有两种选择：选或者不选数组n位置所在的数，如果选择n，那它的值就为arr[n]+opt[n-2],如果不选择n，那它的值就为opt[n-1]。而opt(n)就是两种选择中的最大值。假如我们求opt(6),那么就如下图所示：

那递归出口就是opt(1)=arr[1],opt(2)=max(arr[2],opt(1)),因此我们可以得出如下代码(在此代码中由于数组从0开始，因此在相应的地方-1)：

#include <iostream>
using namespace std;
int arr[7] = {1, 2, 4, 1, 7, 8, 3};

int rec(int arr[], int i) {
    if (i == 0) return arr[0];
    else if (i == 1) return max(arr[0], arr[1]);
    else {
        int A = rec(arr, i - 2) + arr[i];
        int B = rec(arr, i - 1);
        return max(A, B);
    }
}
int main() {
    cout << rec(arr, 6);
}

毫无疑问我们也计算了重叠子问题，由上面的动态规划可知，我们可以通过创建数组来保存相应的值，以此减少不必要的计算，因此，动态规划的代码如下：

#include <iostream>
using namespace std;
int arr[7] = {1, 2, 4, 1, 7, 8, 3};
int opt[7];

int rec(int arr[], int j, int opt[]) {
    opt[0] = arr[0];
    opt[1] = max(arr[0], arr[1]);
    for (int i = 2; i < 7; i++) {
        int A = opt[i - 2] + arr[i];
        int B = opt[i - 1];
        opt[i] = max(A, B);
    }
    return opt[j];
}
int main() {
    cout << rec(arr, 6, opt);
}

好，我们来思考，开辟一维内存的原因是其中只能找到一个变量，如前n个工作的最大薪水、前n个数的最大值，那当我们存在多个变量时又该如何求解呢？所以我们引出二维动态规划。

第二类问题（二维）

1.选取数字

给定一个数，我们是否可以在如下数组中找到任意个数，使选中的所有数值之和等于给定的数，如果可以找到，则返回true，如果不可以找到，则返回false。

首先我们先用递归的思想来看这道题，假如给定一个数9，我们怎样写出一个算法来让计算机判断数组中是否有任意个数之和为9呢？还是老套路，我们创建一个递归函数，传给它数组、数组的最后一个下标（此题为5）、目标值。我们从数组中第六个元素开始看，我们有两种选择：第一种，我们选择这个元素，如果选择的话，那么我们接下来调用递归函数，它的实参就是数组、此下标数减1、目标数减此下标的值（因为我们选了这个下标上的值，所以应该把值减去）；第二种，我们不选择这个数，那么我们接下来调用递归函数，它的实参就是数组、此下标数减1、目标数。如果这两种选择有一种能够成功找出结果，那么就返回true,如果两种选择都不满足，那么则返回false即可。

接下来我们要思考递归的中止条件：

1.当目标值被减为0时，直接返回true

2.当下标数为0时，如果下标0对应的数组值不等于此时的目标值，则返回false

3.当选择此下标值时，如果此下标对应的数组值大于目标值，则不能做此选择

好，既然确定了终止条件，那么我们来看代码：

#include <iostream>
using namespace std;

int arr[6] = {3, 34, 4, 12, 5, 2};

int rec_subset(int arr[], int i, int s) {
    if (s == 0)
        return true;
    else if (i == 0)
        return arr[0] == s;
    else if (arr[i] > s)
        return rec_subset(arr, i - 1, s);
    else {
        bool A = rec_subset(arr, i - 1, s - arr[i]);
        bool B = rec_subset(arr, i - 1, s);
        return A or B;
    }
}
int main() {
    cout << rec_subset(arr, 5, 13);
}

由于此递归重复了大量重复子问题，接下来我们要思考的是，怎样用动态规划的方式从前往后做这道题？

首先我们判断此动态规划为二维问题，因为有两个东西可以作为二维数组的两个下标：目标值、arr数组中的元素的下标。因为我们从刚才的递归可以看出目标值从后往前是不断递减的，因此我们就可以从0开始往后递增，arr数组中的元素的个数也可以依次增加，所以作为二维数组的另一个下标。因为我们返回的是布尔值，所以我们需要建立二维布尔数组如下：

这就是我们要保存每个数据的二维数组，第一行代表的是目标值从1到9，列代表的是下标数，每个格子代表用当前的元素可否能找出数据使其和等于目标值，那怎么样填此二维数组呢？

现在我们来思考一下我们上面所想到的终止条件：

1.当目标值被减为0时，直接返回true，所以第一列都为true

2.当下标数为0时，如果下标0对应的数组值不等于此时的目标值，则返回false，因此第一行除了3等于第0个元素对应的数组数据为true外，其余都为false

因此我们可以把此表改成如下：

我们用T代表true，用F代表false，其中第0行第0列是T或者F都可以。

接下来我们就可以给二维数组里面的其他元素赋值了，比如第i行j列，我们先判断i下标对应的数组元素值是否大于j（目标元素）。

如果不大于，那么就可以分为两种情况：第一种，其值等于行为i-1，列为j-arr[i]的值(代表选了此下标对应的数)；第二种行为i-1，列为j(代表没有选此下标对应的数)。当两种情况有一种以上为T时，第i行j列的值就为T，否则就为F。

如果大于，意为我们不能选择此时对应的元素值，因为如果选择的话，目标值就变为负数了，所以我们仅有一种选择，那么第i行j列的值就等于i-1行j列的值。

以此类推，填满此二维数组，最终的值为二维数组最右下角的值。我们来看代码：

#include <iostream>
using namespace std;

int arr[6] = {3, 34, 4, 12, 5, 2};

bool dpsubset(int arr[], int s) {
    bool subset[6][s + 1];
    for (auto j : subset) {
        j[0] = true;
    }
    for (auto &j : subset[0]) {
        j = false;
    }
    subset[0][arr[0]] = true;
    for (int h = 1; h < 6; h++) {
        for (int k = 1; k < s + 1; k++) {
            if (arr[h] > k)
                subset[h][k] = subset[h - 1][k];
            else {
                bool A = subset[h - 1][k];
                bool B = subset[h - 1][k - arr[h]];
                subset[h][k] = A or B;
            }
        }
    }
    return subset[5][s];
}

int main() {
    cout << dpsubset(arr, 13);
}

由此问题引出另外一个问题，我们怎样求得我们选择的是哪些数呢？别急，看了下面的题目，我们就会解决了。

2.背包回溯

现在有四个物品，背包的总容量为8，背包最多能装入价值为多少的物品？都装了哪些物品？

毫无疑问，这是二维动态规划，怎么判断的呢？因为它有两个东西可以作为二维数组的两个下标，一个是物品编号，一个是背包容量，所以我们创建二维数组如下：

其中第一行代表背包容量，第一列代表物品个数，每个格子为在当前背包容量的情况下考虑当前的物品所能装下的最大价值是多少。

现在我们来填格子，首先第二行全部为0，因为此时没有物品；其次第二列为0，因为此时背包容量为0。现在我们来填其余表格，在填之前，我们先考虑当前格子对应的物品是否能装入背包。

如果能装下当前物品，那么分两种情况：第一种为装入背包，获得此物品的价值，然后减去它所占的空间，找对应剩余空间容量、物品数减一对应的最大价值（就是找之前的格子），然后两个价值相加；第二种为不装，那么当前最大价值等于对应空间容量不变、物品数量减一的最大价值（就是此格子头顶的格子）。最后此格子的值等于两种情况中最大的值。

如果不能装入背包，那么当前最大价值等于对应空间容量不变、物品数量减一的最大价值（就是此格子头顶的格子），最后此格子的值等于此格子头顶上的格子的值。

在我们填满二维数组后，来考虑一下新的问题：回溯，如何找到背包放的物品编号？

我们先从二维数组最右下角的格子找，如果它的值等于它头顶上的格子，则证明它没装此时对应的物品，否则就是装了此物品，这个格子的值等于这个格子的两个下标分别减一和此时放入背包的物品的所占空间的格子对应的值加上这个格子对应的物品价值，开辟一个数组，这样回溯，如果找到放入的物品，则在此数组对应的位置上设为1，没放入此物品则在数组对应的位置上设为0,最后输出数组即可，大家看代码：

/*
i物品编号 1   2   3   4
w体积    2   3   4   5
v价值    3   4   5   6
*/
#include <iostream>
using namespace std;
int weight[5] = {0, 2, 3, 4, 5};
int value[5] = {0, 3, 4, 5, 6};
int dp[5][9];
int object[5];

void Dynamic() {
    for (int i = 1; i < 5; i++) {
        for (int j = 1; j < 9; j++) {
            if (weight[i] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
}

void Find(int i, int j) {
    if (i == 0) {
        for (int i = 0; i < 5; i++)
            cout << object[i] << " ";
        return;
    }
    if (dp[i][j] == dp[i - 1][j]) {
        object[i] = 0;
        Find(i - 1, j);
    } else if (dp[i][j] == dp[i - 1][j - weight[i]] + value[i]) {
        object[i] = 1;
        Find(i - 1, j - weight[i]);
    }
}
int main() {
    Dynamic();
    cout << dp[4][8];
    Find(4, 8);
}

延伸

如果你看到这里，并且认真看完上述文字后，恭喜你初步掌握了动态规划的常见问题，大家最好把上述代码反复敲几遍，第一遍照着敲，第二表凭借理解单独敲。马化腾曾说过一句话，给我感触很大，“用最笨的方式去领悟编程，用抄代码的方式来培养感觉”。

此外大家就可以不断在各个平台上刷题来提升自己的感觉，一起加油！