动态规划基础[更新中]

动态规划基础

DP 的核心思路

动态规划的思路，是将一个复杂的问题，拆解为多个子问题，然后通过子问题的解推导出问题本身的解——即使用状态方程。

例如一个问题的求解规模是 n，我们可以从规模为 1 的问题开始，使用数组记录他的解（即 dp 数组），然后在规模为 2 的时候可以利用规模为 1 时的解。然后以此类推，一直求出 dp[n] 。DP 思维最简单的体现便是斐波拉契数列。

斐波拉契数列

斐波拉契数列定义为：

F(0) = 0；F(1) = 1; F(n) = F(n-1) + F(n-2)

通过代码不难写出求 F(n) 的函数

int fibonacci(int n)
{
    vector<int> f(n+1, 0);
    f[1] = 1;
    
    for (int i = 2; i <= n; i++)
        f[i] = f[i-1] + f[i-2];
    
    return f[n];
}

实际上斐波拉契数列的定义就是一个典型的 dp 状态转移方程：求解规模为 n 的数组的值与 n - 1 和 n - 2 的和相关。

此外因为只与前两个状态相关，所以实际上 dp 数组的大小可以定义为 2，以此节省空间。

int fibonacci(int n)
{
    vector<int> f(2, 0);
    f[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        int tmp = f[0] + f[1];
        f[0] = f[1];
        f[1] = tmp;
    }

    return f[1];
}

更多题目参考：动态规划题解的一般类型部分

小结

纯动态规划题目的难点主要在于对问题规模的拆分，以及状态转移方程的推导。此外 dp 数组的初始化也是一个需要好好考虑的问题。

动态规划还可以和其他题型相结合组成很复杂的题目，比如对二叉树的 dp，对图的 dp 等。

0-1 背包问题

背包问题是一个非常经典的动态规划的题型大类。其中 0-1 背包是其中最基础的题型，其他的背包问题都是 0-1 背包的衍生。

问题描述

有一组物品，每个物品有两个属性：价值（value）和重量（weight）。有一个最大承重为 M 的背包。求如何选择物品放入背包最后的总价值最大？

例如有如下物品，背包大小为 5 时

物品序号	物品重量	物品价值
0	2	10
1	4	5
2	1	4

思路

使用二维数组保存 dp

问题的规模是 5，那么我们可以将其分解为 背包大小为 0 到 5 的情况下装下物品的最大价值。

此外物品有 3 个，每一个物品都可以分为选与不选。所以需要一个二维数组。

dp[i][j] 表示，考虑到有 [0, i] 物品时，背包大小为 j 时的最大价值。不难推出状态转移公式：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i].weight] + items[i].value)

• dp[i-1][j] 表示不选第 i 个物品时的最大价值，即从 0 到 i - 1 个物品这个子问题的最大价值。

• dp[i-1][j-item[i].weight] + item[i].value 表示放入第 i 个物品时的最大价值。

  • dp[i-1][j-item[i].weight] 表示从当前的背包大小减去第 i 个物品的重量时的最大价值，

    这样再加上当前物品的价值就可以得到放入第 i 个物品时的最大价值。

带入上述的例子便可以计算出 dp 数组，而 dp[2][5] 便是我们最终问题规模的解。

物品/背包大小	0	1	2	3	4	5
0	0	0	10	10	10	10
1	0	0	10	10	10	10
2	0	4	10	14	14	14

使用一维 DP 数组

从二维的递推公式（状态转移方程）可以看出，dp[i][j] 只与 i-1 层的数相关。所以可以将 DP 数组压缩为一维数组，递推公式如下：

dp[j] = max(dp[j], dp[j - items[i].weight] + items[i].value)

• dp[j] 表示从第一个物品遍历到当前物品时，背包大小为 j 的最大价值。我们只需在每层循环下更新 dp[j] 到当前物品就可以了。

需要注意的是，一维 DP 数组背包大小的遍历顺序对于结果是有影响的。

vector<int> solution(vector<vector<int>>& items, int size)
{
    vector<int> dpMaxVal(size+1, 0);		// 最大价值优先
    vector<int> dpMaxBag(size+1, INT_MIN);	// 装满背包优先
    dpMaxBag[0] = 0;
    for (vector<int>& item: items)
    {
        for (int i = size; i >= item[0]; i--)
        {
            dpMaxVal[i] = max(dpMaxVal[i], dpMaxVal[i-item[0]] + item[1]);
            dpMaxBag[i] = max(dpMaxBag[i], dpMaxBag[i-item[0]] + item[1]);       
        }
    }

    return {dpMaxVal[size], dpMaxBag[size] >= 0 ? dpMaxBag[size] : 0};
}

完全背包问题

组合

先物品后背包

排列

先背包后物品