b站视频链接：北京理工大学ACM冬季培训课程
未找到课程习题
本篇博文为看视频学习时的记录与自己的一些总结

动态规划DP

¶什么是动态规划？

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

¶两个问题

解决动态规划问题，要明确状态和转移两个问题。

¶【例】数字三角形

给出一个数字三角形，从顶点出发每次向下或右下走一步直至最底层，将途经的数字相加，问得到的最大值。

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

7->3->8->7->5 = 30

¶状态

定义状态 $f[i][j]$ 表示从 $(1, 1)$ 出发走到 $(i, j)$ 所有路径的最大和。

例如：$f[3][2] = \text{max}(7+3+1, 7+8+1) = 16$

答案从哪取：$f[n][1 \dots n]$

¶转移

考虑哪些状态对 $f[i][j]$ 这个状态有影响。

$(i-1, j) \rightarrow (i, j)$

$(i-1, j-1) \rightarrow (i, j)$

如何转移？

$f[i][j] = \text{max}(f[i-1][j], f[i-1][j-1]) + a[i][j]$

把 $(1, 1)$ 到 $(i, j)$ 的路径分成两类，$(1, 1) \rightarrow (i-1, j) \rightarrow (i, j)$ 和 $(1, 1) \rightarrow (i-1, j-1) \rightarrow (i, j)$

¶初始状态&取答案

状态要明确两点

初始状态 $f[1][1] = a[1][1]$，其余为 $-\text{inf}$
答案在哪取 $\text{max}(f[n][1] \dots f[n][n])$

转移要注意顺序

从上到下，从左到右

For i:2->n
    For j:1->l
        f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];

¶【例】经典问题最长上升子序列 (LIS)

给一个序列，求它的最长上升子序列。
其中，子序列是指将序列删除 $0 - n$ 个元素所组成的序列，子序列不一定是连续的。

1 13 5 7 8 2 11
1 5 7 8 11

¶状态

$f[i]$ 表示以 $i$ 结尾的上升子序列中的最长长度。

¶转移

$f[i] = max(f[j]) + 1$，$i < j$ 且 $a[i] < a[j]$

¶初始状态&取答案

初始状态 $f[i] = 1$
取答案 $ans = \text{max}(f[1] \dots f[n])$

For i = 1->n
{
    f[i] = 1;
    For j = 1->i-1 
        if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1)
}

时间优化

可以优化成 $O(n \log n)$
用二分的方法

¶更多经典问题

最长公共子序列
最大子段和
最长公共上升子序列

杨辉三角

    0 1 2 3 4
0   1
1   1 1
2   1 2 1
3   1 3 3 1
4   1 4 6 4 1

c[n][m] = C[n-1][m] + C[n-1][m-1];

¶背包问题

¶01 背包问题

给 $n$ 个物品，每个物品有体积 $v_i$ 以及价值 $w_i$，取 $n$ 个物品的一个子集，使得体积和不超过 $m$，并且价值和尽量大。

如果采用贪心的方法取，肯定能举出反例。

状态

$f[i][j]$ 表示考虑前 $i$ 个物品，占用体积为 $j$，能得到的最大价值。

转移

$f[i][j]=\text{max}(f[i-1][j], f[i-1][j-v[i]]+w[i])$
考虑第 $i$ 个物品取还是不取
取则从 $f[i - 1][j-v[i]]+w[i]$ 转移过来
不取则从 $f[i-1][j]$ 转移过来

空间优化

（图解）

滚动数组

数组 $f[i][j]$ 的取值只与上一行有关，开数组 $f[2][maxn]$
用 $f[i%2][j]$ 代表当前行
用 $f[(i-1)%2][j]$ 代表上一行

进一步优化

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

从后向前更新，$j$ 以后的是当前行，$j$ 以前的是上一行。

¶完全背包

与 01 背包不同，每个物品可以不限制次数取。

转移方程略作修改

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

¶更多背包问题

多重背包：二进制拆分
混合背包：01，完全，多重背包的混合
二维费用背包
分组背包
背包九讲

二进制拆分图解