【算法】动态规划(dp)_dp动态规划

目录

1 引例

2 动态规划原理

2.1 最优子结构

2.2 无后效性

2.3 子问题重叠

2.4 基本思路

3 二维: 0-1背包问题

---

动态规划（Dynamic Programming, DP）是运筹学的一个分支，是求解决策过程最优化的过程。

1 引例

洛谷P1216

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5 

在上面的样例中,从 7→3→8→7→5 的路径产生了最大。

一条最优的路径，它的每一步决策都是最优的。

以例题里提到的最优路径为例，只考虑前四步7→3→8→7，不存在一条从最顶端到 4 行第 2 个数的权值更大的路径。

而对于每一个点，它的下一步决策只有两种：往左下角或者往右下角（如果存在）。因此只需要记录当前点的最大权值，用这个最大权值执行下一步决策，来更新后续点的最大权值。

这样做还有一个好处：我们成功缩小了问题的规模，将一个问题分成了多个规模更小的问题。要想得到从顶端到第 r 行的最优方案，只需要知道从顶端到第 r - 1 行的最优方案的信息就可以了。

这时候还存在一个问题：子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。解决这个问题的方法是把每个子问题的解存储下来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。

以上用一个简单的典例介绍了动态规划的基本思路。

---

2 动态规划原理

能用动态规划解决的问题，需要满足三个条件：

1. 最优子结构
2. 无后效性
3. 子问题重叠

2.1 最优子结构

具有最优子结构也可能是适合用贪心的方法求解。注意要确保我们考察了最优解中用到的所有子问题。子问题的解每一步也是最优的。

1. 证明问题最优解的第一个组成部分是做出一个选择；
2. 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
3. 给定可获得的最优解的选择后，确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间；
4. 证明作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。
   用反证法，考虑加入某个子问题的解不是其自身的最优解，那么就可以从原问题的解中用该子问题的最优解替换掉当前的非最优解，从而得到原问题的一个更优的解，从而与原问题最优解的假设矛盾。

最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题；
2. 确定最优解使用哪些子问题时，需要考察多少种选择。

2.2 无后效性

已经求解的子问题，不会再受到后续决策的影响。

也就是说，假如总共有n个状态，则某个状态  之后的所有状态  的结果与之前的历史状态  都无关，只和  有关。

更具体来说，在最长公共子序列问题里面：

“输10个字符，求到第5个字符的最长子序列 的结果”

和

“只输前面5个字符，求到第5个字符（最后一个）的结果”

一样。

2.3 子问题重叠

如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

2.4 基本思路

1. 将原问题划分为若干 阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为 状态）；
2. 寻找每一个状态的可能 决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 按顺序求解每一个阶段的问题。

状态转移方程：

给定k阶段状态变量  的值后，如果这一阶段的决策变量一经确定，第  阶段的状态变量 也就完全确定，即 的值随  和第 k 阶段的决策  的值变化而变化，那么可以把这一关系看成  与  确定的对应关系，用 表示。这是从 k 阶段到 k+1 阶段的状态转移规律，称为状态转移方程。

---

3 二维: 0-1背包问题

洛谷P1048 采药

0-1背包问题与背包问题的区别在于：一个物品不能细分成只拿一部分，只能选择拿或不拿。这就导致我们不能运用贪心策略来求解0-1背包问题。

实际上，要求解 0-1背包问题，我们需要先求解子背包问题，然后逐步求得总背包的答案。也就是先求解背包容量很小的情况下的最优状态，然后逐步扩容，每次扩容仍然保证其状态最优。

 ᕙ(`▿´)ᕗ ↓

我们需要定义一个二维数组，将它想象成一个矩阵，每一行表示一棵草药，每一列表示目前所给你的时间。在第 i 行，我们可以摘前 i 棵草药中的任意多棵，只要时间允许。而且要使这种状态下的价值  最大。第 i 行的值与第 i - 1 行的值相关。

第一层循环遍历每种药品，序号 i 及之前的药品均有可能放入。第二层循环遍历时间，当前允许使用的最大时间（相当于子背包）。

只有当前给出的最大时间足够采摘当前这一株草药的时候，才判断是否采摘当前的这一株草药。如果总时间 j 足够采摘药品 i ，
此时取

“前一行同列（同一时间下前一个状态）的dp值” (不采摘i)  

和

“当前药品的价值 + 除去采i药品的时间，剩余时间可采的最大药品价值” (采摘i)

两者中更大的那个。

如果  ，说明所给的时间一定不足以摘 i 号药品，

那么此时的  一定不会被更新，只能使  。即按之前的 i-1 行同列状态来算。

本题行列循环互换不影响结果，但有些二维dp的题目对循环的顺序有要求。

( ´◔︎ ‸◔︎`)

推荐同学们看《算法图解》第九章，其中对 0-1 背包问题作了详细生动的讲解。

以下是AC代码（含详细注释）：

#define MAX_SIZE 105
 
struct Drug //药的结构体，包含药的价值和采摘时间
{
    int value[MAX_SIZE];
    int time[MAX_SIZE];
};
int dp[MAX_SIZE][1005]; //存储当前状态最大价值。横纵坐标分别表示当前药序号和目前最大可消耗时间
 
int maxValue(int time, int n, Drug &d) {
    for (int i = 1; i <= n; i++) {
    //第一层循环遍历每种药品，序号i及之前的药品均有可能放入，但i之后的尚未考虑
        for (int j = 1; j <= time; j++) {
        //第二层循环遍历时间，j表示当前允许使用的最大时间
        //只有给出的总时间j足够采摘当前这一株草药的时候(j >= d.time[i]),
        //才判断是否采摘当前的这一株草药，否则一定只能按之前的i-1状态来算。
            if (j >= d.time[i]) {
                //如果总时间j足够采摘药品i，
                //取“前一行同列（同一时间下前一个状态）的dp值” (不采摘i) 
                //和 “当前药品的价值 + 除去采i药品的时间，剩余时间可采的最大药品价值” (采摘i)
                //两者中更大的那个
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - d.time[i]] + d.value[i]);
            }
            else {
                //如果总时间j不足够采摘药品i，
                //即(j <= d.time[i])则直接取前一行同列（同一时间下的前一个状态）的dp值。
                //(进不去，怎么想都进不去嘛！)
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][time]; //返回最后一个状态，即给的时间为总时间t且所有药品都可以采
}
 
int main()
{
    int t, m; //采药时间，草药数目（相当于背包容量和物品数量）
    int ans = -1;
    Drug d;
 
    cin >> t >> m;
    for (int i = 1; i <= m; i++) {
        cin >> d.time[i] >> d.value[i];
    }
 
    ans = maxValue(t, m, d); //emmm...不是故意用这三个字母...写完才发现orz
    cout << ans;
}

---

本文理论部分大部分参考自OI Wiki。

谢谢您的阅读。欢迎朋友们指出错误，友好讨论。