动态规划算法DP

动态规划，Dynamic Programming，简称 DP。

动态规划并不是某一种固定的算法，而是一种解决问题的方法。

很多问题如果直接递归，会反复计算大量相同的子问题。DP 最直接的想法就是：

已经算过的东西，不要再算第二遍。

把小问题的答案保存下来，再利用这些已经得到的答案继续推出更大的问题。

大概就是：

大问题
 ↓
拆成小问题
 ↓
保存已经求出的答案
 ↓
利用已有答案继续转移
 ↓
得到大问题答案

真正做 DP 的时候，最重要的不是先写代码，而是先把几个东西想清楚：

状态
状态转移方程
初始状态
计算顺序

尤其是第一步。

看到一道 DP，最好先问：

f[i] 到底表示什么？

如果状态本身都没有定义清楚，后面的转移基本也很难写对。

从Fibonacci开始

先看最简单的 Fibonacci 数列。

定义：

$$ F_1=1,\qquad F_2=1 $$

对于：

$$ n\geq3 $$

有：

$$ F_n=F_{n-1}+F_{n-2} $$

如果直接递归：

int fib(int n)
{
    if (n <= 2)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

代码非常简单，但是会产生大量重复计算。

例如：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

可以看到：

fib(3)
fib(2)
fib(1)

都会反复出现。

但是同一个：

fib(3)

不管算多少遍，答案永远都是一样的。

既然这样，就没有必要每次重新递归。

可以直接开一个数组：

int f[1000];

然后定义：

f[i]
=
Fibonacci 数列的第 i 项

初始状态：

f[1] = 1;
f[2] = 1;

状态转移：

$$ f_i=f_{i-1}+f_{i-2} $$

所以代码可以直接从前往后递推：

#include <cstdio>

int f[1000];

int main()
{
    int n;

    scanf("%d", &n);

    f[1] = 1;
    f[2] = 1;

    for (int i = 3; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];

    printf("%d\n", f[n]);

    return 0;
}

这里已经有了 DP 最基本的结构：

定义状态
 ↓
找到以前已经求出的状态
 ↓
写出状态之间的关系
 ↓
按照正确顺序计算

所以以后写 DP，我觉得最好先强迫自己写一句：

f[i] 表示……

或者：

f[i][j] 表示……

先把这一句话写明白，再往下想。

DP到底要想什么

一般可以按照下面几个问题往下拆。

首先：

状态是什么？

例如：

f[i]

可能表示处理到第 i 个位置时的最优答案。

也可能是：

f[i][j]

表示只处理前 i 个元素，并且当前还处于状态 j 时的答案。

状态定义以后，再问：

当前状态能够由哪些以前的状态得到？

例如：

f[i] = max(f[i - 1], f[i - 2] + a[i])

或者背包里：

$$ f_{i,j} = \max \left( f_{i-1,j}, f_{i-1,j-w_i}+v_i \right) $$

这就是状态转移。

然后还要考虑边界和初始状态。

例如：

f[0] = 0;

或者：

f[1][1] = a[1][1];

最后还要想：

按照什么顺序算？

因为当前状态依赖的一定应该是：

已经计算完成的状态

如果计算顺序反了，就可能拿到本轮刚刚更新过的数据，最后完全变成另外一个问题。

所以我现在感觉，一道 DP 至少先问四遍：

f 表示什么？
 ↓
从哪里转移？
 ↓
边界是什么？
 ↓
按照什么顺序计算？

数字三角形

看一个很典型的二维 DP。

例如：

从最上面开始，每一步只能走到下一行相邻的位置，求走到底部以后经过数字的最大和。

定义：

f[i][j]

表示：

从三角形顶部走到第 i 行第 j 个位置时，能够得到的最大数字和。

考虑当前位置：

(i, j)

它只能从上一行两个位置过来：

(i - 1, j - 1)

或者：

(i - 1, j)

所以状态转移就是：

$$ f_{i,j} = \max \left( f_{i-1,j-1}, f_{i-1,j} \right) + a_{i,j} $$

也就是说：

当前位置最优答案
=
所有能够走到当前位置的前驱状态中取最大值
+
当前位置自己的贡献

这就是很标准的 DP。

边界需要单独注意。

最左边：

(i, 1)

只能从：

(i - 1, 1)

过来。

最右边：

(i, i)

只能从：

(i - 1, i - 1)

过来。

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int a[1005][1005];
int f[1005][1005];

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);

    f[1][1] = a[1][1];

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (j == 1)
            {
                f[i][j] = f[i - 1][j] + a[i][j];
            }
            else if (j == i)
            {
                f[i][j] = f[i - 1][j - 1] + a[i][j];
            }
            else
            {
                f[i][j] =
                    max(
                        f[i - 1][j - 1],
                        f[i - 1][j]
                    )
                    + a[i][j];
            }
        }
    }

    int ans = 0;

    for (int j = 1; j <= n; j++)
        ans = max(ans, f[n][j]);

    printf("%d\n", ans);

    return 0;
}

这里状态有：

$$ 1+2+\cdots+n = \frac{n(n+1)}{2} $$

所以状态数量为：

$$ O(n^2) $$

每个状态最多只需要检查两个前驱，因此转移是：

$$ O(1) $$

总时间复杂度就是：

$$ O(n^2) $$

01背包

背包应该算 DP 里面非常经典的一类。

现在有 n 个物品，第 i 个物品有：

重量 w[i]
价值 v[i]

背包最大容量为：

每个物品只能选择：

0次
或
1次

要求总重量不超过容量的情况下，让总价值最大。

这就是：

01背包

先不急着压空间，直接定义二维状态：

f[i][j]

表示：

只考虑前 i 个物品，背包容量为 j 时能够得到的最大价值。

处理第 i 个物品时，其实只有两个选择。

不选第i个物品

那么：

$$ f_{i,j}=f_{i-1,j} $$

选择第i个物品

首先必须满足：

$$ j\geq w_i $$

选了以后，第 i 个物品占用 w[i] 容量，所以剩余容量为：

$$ j-w_i $$

前面的最优价值就是：

$$ f_{i-1,j-w_i} $$

再加上当前物品：

$$ f_{i-1,j-w_i}+v_i $$

所以最终状态转移：

$$ f_{i,j} = \max \left( f_{i-1,j}, f_{i-1,j-w_i}+v_i \right) $$

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int w[1005];
int v[1005];
int f[1005][1005];

int main()
{
    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];

            if (j >= w[i])
            {
                f[i][j] =
                    max(
                        f[i][j],
                        f[i - 1][j - w[i]] + v[i]
                    );
            }
        }
    }

    printf("%d\n", f[n][m]);

    return 0;
}

01背包空间压缩

继续观察：

f[i][j]

会发现第 i 行只依赖：

f[i - 1][...]

更早的：

f[i - 2]
f[i - 3]
...

已经没有用了。

所以可以把第一维删掉，只保存：

f[j]

表示：

当前已经处理过的物品中，容量为 j 时能够得到的最大价值。

转移变成：

$$ f_j = \max \left( f_j, f_{j-w_i}+v_i \right) $$

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int w[1005];
int v[1005];
int f[10005];

int main()
{
    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= w[i]; j--)
        {
            f[j] =
                max(
                    f[j],
                    f[j - w[i]] + v[i]
                );
        }
    }

    printf("%d\n", f[m]);

    return 0;
}

这里有一个很重要的地方：

for (int j = m; j >= w[i]; j--)

容量必须倒序。

为什么？

假设：

w[i] = 2
v[i] = 3

如果容量从小到大更新，先：

f[2] = f[0] + 3

然后继续：

f[4] = f[2] + 3

但是这里的：

f[2]

已经是当前这一轮刚刚使用过第 i 个物品以后得到的新状态。

所以：

f[4]

实际上又把第 i 个物品使用了一次。

同一个物品被用了两遍，这就不再是：

01背包

了。

因此必须倒序，让：

f[j - w[i]]

在当前这一轮还保持为“没有使用第 i 个物品”的上一轮状态。

完全背包

如果题目变成：

每种物品可以选择任意多次。

那就是：

完全背包

一维状态转移看起来还是：

$$ f_j = \max \left( f_j, f_{j-w_i}+v_i \right) $$

但是遍历顺序反过来了：

for (int i = 1; i <= n; i++)
{
    for (int j = w[i]; j <= m; j++)
    {
        f[j] =
            max(
                f[j],
                f[j - w[i]] + v[i]
            );
    }
}

完全背包中，容量从小到大。

因为它本来就允许：

同一个物品重复使用

所以当前这一轮刚刚更新出来的：

f[j - w[i]]

可以继续参加后面的转移。

这样看：

01背包
容量倒序

完全背包
容量正序

当然可以直接记。

但是我觉得更重要的是知道为什么。

真正应该问的是：

当前这一轮已经更新过的状态，允不允许再次使用当前这个物品？

如果不允许，就是01背包，倒序。

如果允许，就是完全背包，正序。

这样就不用死背了。

最长上升子序列

再看一个和背包完全不一样的 DP。

给出：

3 1 2 5 4

要求找一个严格递增的子序列，使长度最大。

例如：

1 2 5

或者：

1 2 4

长度都是：

这就是：

Longest Increasing Subsequence

简称：

LIS

定义：

f[i]

表示：

以第 i 个元素作为结尾的最长上升子序列长度。

这里“以第 i 个元素结尾”很重要。

考虑所有：

$$ j\lt i $$

如果：

$$ a_j

那么 a[i] 就可以接到一个以 a[j] 结尾的上升子序列后面。

所以：

$$ f_i = \max_{\substack{j\lt i\\a_j

当然，如果前面一个都接不上，a[i] 自己也可以组成长度为1的上升子序列。

因此初始化：

f[i] = 1;

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int a[1005];
int f[1005];

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);

    int ans = 0;

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;

        for (int j = 1; j < i; j++)
        {
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        }

        ans = max(ans, f[i]);
    }

    printf("%d\n", ans);

    return 0;
}

这里有：

n 个状态

每个状态又需要往前枚举最多：

n 个位置

所以复杂度是：

$$ O(n^2) $$

LIS 后面当然还可以继续优化，不过刚开始理解 DP 的时候，这个写法更重要。

因为它把状态转移表现得很清楚：

确定当前状态
 ↓
枚举所有可能的前驱状态
 ↓
检查这个前驱能不能转移
 ↓
取其中最优

递推DP与记忆化搜索

很多 DP 其实都可以先从递归想。

还是 Fibonacci：

fib(n)

会继续调用：

fib(n - 1)
fib(n - 2)

这是从目标问题不断向更小的问题走：

自顶向下

如果给递归加一个数组，把已经计算过的值保存下来：

if (f[n] != -1)
    return f[n];

就变成记忆化搜索。

例如：

int f[1000];

int solve(int n)
{
    if (n <= 2)
        return 1;

    if (f[n] != -1)
        return f[n];

    return f[n] = solve(n - 1) + solve(n - 2);
}

它和普通递推 DP 的核心其实是一样的：

不要重复计算已经求过的状态。

主要区别在计算方向。

记忆化搜索
=
从目标状态开始递归
需要哪个子问题就计算哪个

递推DP
=
从初始状态开始
按照已经确定的顺序不断向后计算

很多问题其实两种方法都能写。

如果递归关系很好想，记忆化搜索往往比较自然。

如果状态之间的计算顺序本身已经非常清楚，直接递推通常更方便。

DP为什么能成立

现在回头看，动态规划其实有一个很重要的地方：

如果两个不同的过程最后到达了同一个状态，而这个状态已经保存了以后继续决策所需要的全部信息，那么之前到底是怎么走到这里的，后面就没有必要再分别讨论。

例如背包里的：

f[i][j]

只关心：

已经处理到第几个物品
当前容量是多少

只要这两个条件相同，前面到底具体选了哪些物品，如果已经体现在最优价值 f[i][j] 里面，那么以后继续转移时就没有必要把所有历史重新保存下来。

所以设计状态的时候，实际上是在做一件事：

把对未来仍然有用的信息留下，把以后已经不需要的信息扔掉。

这也是为什么有些题：

f[i]

就够了。

而有些题必须：

f[i][j]

甚至：

f[i][j][k]

状态维数不是越多越好。

每增加一个维度，状态数量、时间和空间往往都会跟着增加。

所以真正需要记录的是：

以后还会影响答案的信息

DP真正难在哪里

动态规划真正难的显然不是：

for
max
数组

这些东西。

真正难的是：

状态怎么定义？

以及：

状态之间到底是什么关系？

看到一道题要求：

最大值

不能直接说：

这是DP

还是要继续看。

比如：

大问题能不能拆成更小的问题？

不同计算过程会不会反复遇到相同的子问题？

当前答案能不能利用已经求出的答案继续推出？

能不能设计一个有限的状态，
把以后真正还需要的信息保存下来？

如果这些东西能够做出来，才比较像一个 DP。

所以我现在觉得，看到 DP 题先别急着套模板。

先写：

f 表示什么？

只要这个东西真的定义清楚，后面很多东西都会自然很多。

复杂度

DP 也不代表一定快。

状态设计出来以后，还要看：

这些状态到底算不算得完？

一个比较直接的估计：

$$ \text{时间复杂度} \approx \text{状态数量} \times \text{每个状态枚举的转移数量} $$

例如数字三角形：

状态数量 O(n²)
每个状态 O(1) 转移

所以：

$$ O(n^2) $$

普通 LIS：

状态数量 O(n)
每个状态最多枚举 O(n) 个前驱

所以：

$$ O(n^2) $$

如果设计一个：

f[i][j]

并且：

i <= 10000
j <= 10000

那么光状态数量就已经有：

$$ 10^4\times10^4=10^8 $$

如果每个状态里面还要继续枚举，基本就更难接受。

所以写完状态转移以后，还要继续问：

有多少状态？
每个状态要枚举多少东西？
总复杂度是多少？

空间优化

空间也是一样。

例如：

f[i][j]

如果第 i 层永远只依赖：

f[i - 1][...]

那么第：

i - 2
i - 3
...

这些更早的状态就已经没有用了。

这时可以考虑：

滚动数组

或者像01背包一样直接压成：

一维数组

不过我觉得刚开始学 DP 的时候，不要一上来就为了省一点空间把状态压得完全看不懂。

更合理的顺序还是：

先定义清楚状态
 ↓
先写出最直接的DP
 ↓
确定状态转移正确
 ↓
再看哪些旧状态已经不会使用
 ↓
进行空间优化

空间压缩应该是从状态依赖关系里面推出来的，而不是直接背：

这题要用一维数组

总结

现在把 DP 整个过程放在一起，大概就是：

定义状态
   ↓
确定状态表示什么
   ↓
寻找前驱状态
   ↓
写出状态转移方程
   ↓
处理初始状态和边界
   ↓
确定计算顺序
   ↓
检查时间和空间复杂度
   ↓
得到答案

以后应该还会继续遇到：

线性DP
背包DP
区间DP
树形DP
数位DP
状态压缩DP

这些名字当然都不一样，但是最前面的东西其实还是一样的。

先问：

f 到底表示什么？

再问：

当前这个 f
可以从哪些已经求出的状态得到？

然后继续检查：

边界是什么？
计算顺序是什么？
有多少状态？
每个状态需要多少转移？
能不能压空间？

只要最开始的状态定义和状态转移真正想明白，代码往往已经写完一半了。

DP 不是把几个公式背下来。

它更像是把一个大问题拆开以后，把已经得到的小问题答案留下，再利用这些答案一步一步把后面的状态推出来。