知识库 · 文字讲解,AI 整理
动态规划
动态规划的条件是:不同的路径会走到同一个状态,而且这个状态往后怎么走与怎么来的无关。这时把每个状态的结果存一次,就不用反复算。从 回溯 加缓存得到的记忆化搜索,和按顺序填表,是同一个东西的两种写法。
三件事要写清楚:状态(一个子问题用什么描述)、转移(它依赖哪些更小的状态)、边界(起点、不可达的状态)。
网格最小代价路径
只能向下或向右走:
LaTeX
$$dp[i][j]=w[i][j]+\min(dp[i-1][j],\,dp[i][j-1]).$$
定好起点和不可达状态,按行或按列填表。有障碍的格子要跳过,不能当成代价为 0 的普通格子。
最长递增路径
只能走向数值严格更大的相邻格子。每一步值都变大,所以这张有向图没有环——这是能用 DP 的前提。记 $dp[i][j]$ 为从 $(i,j)$ 出发的最长路径长度:
LaTeX
$$dp[i][j]=1+\max_{\substack{(u,v)\sim(i,j)\\a[u][v]>a[i][j]}}dp[u][v],$$
没有合法邻居时 max 取 0。可以 DFS 加缓存,也可以按数值从大到小填表。这和 BFS 求无权最短路不同:这里求的是最长的严格递增路径。
更多例子:子集和。
用到它的地方
- 讲义 图的表示、BFS 与 DFS
- 知识库 回溯
- 知识库 图的表示、BFS 与 DFS
- 知识库 前缀和与差分
- 知识库 子集和
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。