[数据结构与算法]DP之引和常用技巧

概论

首先，我们先建立DP和递推之间的联系

也就是我们完全不管前面问题的解决手段，就是疯狂划归子问题

举个栗子昂 4=2+2，2问题解决了呀！（ F[ 2 ]已知 ）好耶！直接抽调，完结撒花！！

我们可以知道，无后效性和最优子结构是动规的精髓，那么判断这两项的能力说白了就是动规之光！！

动规5步大法：

1，划分阶段

2，确立状态

3，讲求策略（找到状态转移方程）

4，特指边界

5，复用最优子结构（有点像记忆化）

你可以试着使用表格分析所有的DP，这篇博客可能是初学者之光
dp分析大法（闫氏的还在路上，施工ing）

01背包的实际情景 和 DP表格分析法

强调：这一系列博客我们直接省略朴素转移代码，只写优化的，但是文字说明和基本的状态转移方程还在

数字三角形模型（偏进阶）

• 适用：二维空间
• 转移：一般固定方向，从那个方向走来就好，很像BFS（最小步数模型）

1，曼哈顿距离

大意：

• 1，给定一个 $n\times n$ 的矩阵，让我们从左上角出发，最终走到右下角
• 2，走过的方块数量的不能超过 $2n?1$ 个
• 3，求所有路线中，经过的方块的总价值最少的路线

曼哈顿距离：两个点在标准坐标系上的绝对轴距总和，$dm=|x1?x2|+|y1?y2|$

起点终点曼哈顿距离：$2n?2$（也可以看作步数）
所以不能乱走（其实也行hh，看数据范围咯），必须按照曼哈顿定义下的最短路原则
所以只能向下或向右

所以其他的直接普通数字三角形建模

2，双路径（同时数字三角形）

题目来源：
NOIP 2000 方格取数
NOIP 2008 传纸条

题意：

• 固定右向和下向的可行方向，求解有两条走向终点的路径
• 路径要求： 走过的数可以取走，（取一回就不能再取了，取了就成0），使得路径取数最大

考虑直接和数字三角形建立联系
1，走一遍，走过的标记下，使得下一次不要从这里转移（理论上只能通过搜索实现）
2，同时走，走到重复的格子取一次，不是重复的取两次

为什可以同时走：因为到终点方向是固定的，意味着两次走步数肯定一致（为终起点曼哈顿距）

步数一致设成 $K$， 枚举 $x1,x2$ 即为两者都走 $k$ 步时的位置

每个点都能两个方向下来，所以合起来就是4步转移

别忘了判边界！！！（在已知步数的情况下减法，很可能越界！）

AC code 方格取数

AC code 传纸条（几乎一样）

不错的题解

3，方格取数究极版

• 题意：左上角出发，右下角出去，不走重复路，求取到数的最大值
• 难点：上下和右，扩展了上
• DP难点，左边不用说，肯定能转移，最难的是上下不能重复转移
• 方法：多加一维方向，特殊判断上下转移
• tips：十年OI …long long…

简单的思路我们不讨论，这里我们直接考虑一下边界

这个过程其实就是对数字三角形转移的深度理解

由于上下转移的特殊性，我们固定了列号，这产生了新的讨论

• 起点：可以从上下左三个方向合法的进入状态空间

• 第一列：除起点外，谁也不能从左侧或者下部转移，这是违背题意的，唯独可以从上往下走

• 第一行：不能从上部转移，这是越界转移

• 第N行：不能从下部转移，这是越界的

P7074 [CSP-J 2020] 方格取数
边界失误和改正的过程
AC code