线性dp

最基本的dp和dp简介

一种优美的暴力

动态规划可以看做在最优化问题和计数问题中对暴力搜索的优化。

在暴力搜索中，我们要枚举每一步决策，枚举所有的方案。

但在多数问题中，暴力搜索其实会做大量重复工作，重复计算大量中间结果。

动态规划就是把这些中间结果用dp数组记录下来，以便后续利用。

最基本的状态和转移方程的设计比较容易，在NOIP题目中一般占分 $30\sim60$。

最基本的方程的设计并没有特别的技巧。一般来说，

• 动态规划问题的“三大要素”：状态、转移、边界。
• 题目中给的条件都可以加入状态中，题目要求最优化的值就是DP值。
• 转移方程往往根据最后一步决策来设计。

线性dp

状态均沿一个方向转移的dp。

例如最基本的模型——数字三角形和最长上升子序列(LIS)都属于线性dp。

[洛谷P1216 [USACO1.5][IOI1994] 数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216)

$dp[i][j]$表示以第 $i$ 行第 $j$ 列为终点的最大数字和，转移方程为 $dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+val[i][j]$。

Openjudge 2.6 1759 最长上升子序列

一会儿详细的说。

几种优化的方式

因为dp要对于题目而设计转移方程，因此有一些优化方式仅能用例题去表示。

但是，强烈建议能想到dp的题先搞出来最基本的，然后再优化，便于对拍和防止暴零。

无优化

以LIS为例子。

求最长上升子序列和最长不降子序列(注意，是子序列以及不降表示可以相等;对于固定的数组，虽然LIS序列不一定唯一，但LIS的长度是唯一的)。

我们用 $dp[i]$ 表示以第 $i$ 位结尾的LIS长度。

转移时每次都向前找比它小的数和比它大的数的位置，将第一个比它大的替换掉。这样操作虽然LIS序列的具体数字可能会变，但是很明显LIS长度还是不变的，因为只是把数替换掉了，并没有改变增加或者减少长度。

因此，转移方程为：

if (num[i - 1] < num[i])
		dp[i] = dp[i - 1] + 1;
	else
	{
		int big = 2e9, ji = -1;
		for (int j = 1; j < i; j++)
		{
			if (num[j] < big && num[j] >= num[i])
			{
				big = num[j];
				ji = j;
			}
		}
		dp[i] = ji == -1 ? 1 : dp[ji];
	}

比较复杂

减少多余状态

打一个恰当的比方，当你的 $dp$ 状态有$4$个，但是其中一个可以由剩下的$3$个推算得来，则这个状态就可以省略(优化掉)。

改变状态设计

通俗一点，就是换一个dp的思路。

前（后）缀和优化DP

背包问题

背包问题是一类特殊的线性DP问题。其模型应用极为广泛，故单独叙述。