DP模板

发表于 | 更新于: | 次
字数统计: 915 字 | 阅读时长 ≈ 3 分钟

本篇阅读时间可能较长，推荐配合以下歌曲食用 ↓

由于考虑到我太菜了，又找了一个模板题来做,看看能不能有所领悟Orz

贴一个维基百科对动态规划的介绍

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

初中英语级别，我觉得不用翻译都能看懂(其实应该翻译作动态决策比较好)

动态规划是一种通过拆分问题，定义问题和状态之间的关系，从而让问题能以递推或分治来解决

重点是拆分问题，如何拆分问题 是动态规划解决问题的核心

状态 和 状态转移方程 就是如何拆分问题 的核心，换句话说就是大事化小，小事化了，只不过在DP里面是反过来，从小到大

这里借用RXZ鸽鸽(雾)的段对解决DP问题的思路

【DP三连】

　　设计DP算法，往往可以遵循DP三连：

　　我是谁？ ——设计状态，表示局面
　　我从哪里来？
　　我要到哪里去？ ——设计转移

设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，更新能从x走到的一些解。这种DP也是不少的，我们以后会遇到。

　　总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。（这两个词是 @阮止雨 妹妹告诉我的，不知道源出处在哪）

贴个例题(从RXZ鸽鸽的知乎回答下借来的)

例题：最长上升子序列(LIS)

　　最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。
　　e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。

遵循上面的DP三连，我们开始解决问题

第一步

我是谁？

这里的” 我 “很明显就是状态

我们设 Long(N)为 以 X 结尾的上升子序列 ， K为这个数列中的最后一项的值

很明显，我们需要的答案就是

第二步

我从哪里来？

那么Long(X 1) 就可以+ 1，answer就可以等于Long(X 1)

由此可得DP方程

然后上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
int r, dp[1616] = {}, tree[1616] = {};
int main()
{
	int maxx = 0, maxq = 0;
	cin >> r;
	for (int i = 1; i <= r; i++)
	{
		cin >> tree[i];
		dp[i] = 1;
	}
	for (int i = 1; i <= r; i++)
	{
		for (int j = i; j <= r; j++)
		{
			if (tree[i] < tree[j])
			{
				dp[j] = max(dp[i] + 1, dp[j]);
			}
		}
	}
	for (int i = 1; i <= r; i++)
	{
		maxx = max(maxx, dp[i]);
	}
	cout << maxx;
	return 0;
}

其实这篇的核心内容都是从RXZ鸽鸽的知乎回答上搬下来的,但是通过自己写一遍，总结一遍，思路也稍稍拓宽了一点

就算身在弱省我也菜死了，不知道下半年能不能水个省一QAQ