动态规划

什么是动态规划

        DP是运筹学的一个分支，是一种将复杂问题分解成很多重叠的子问题，并通过子问题的解得到整个问题的解的算法。

        在DP中有一些概念：

        状态：就是形如dp[i][j]=val的取值，其中i,j为下标，也是用于描述、确定状态所需的变量，val为状态值。

        状态转移：状态与状态之间的转移关系，一般可以表示为一个数学表达式，转移方向决定了迭代或递归方向。

        最终状态：也就是题目所求的状态，最后的答案。

动态规划的分析步骤

1.确定状态，一般为“到第i个为止，xx为j（xx为k）的方案数/最小代价/最大价值”，可以根据数据范围和复杂度来推理。

2.确定状态转移方程，即从已知状态得到新状态的方法，并确保按照这个方向一定可以正确地得到最终状态。

3.确定最终状态并输出。

线性DP

例题1.建造房屋

解题思路

        本题是一道典型的动态规划问题。具体来说，我们可以使用表示前i条街道中建造j所需的最少成本。

        由于每条街道上至少需要建造一个房屋，因此我们可以将每条街道上的第一个房屋作为基准点。假设前i-1条街道中已经建造了j个房屋，那么对于第i条街道，我们可以考虑在不超过花费预算的情况下，分别建造1，2，···，m个房屋。这样，我们就可以得到状态转移方程：

其中z∈[1,m],

由于建造的总成本不能超过k元，因此最后的答案即为。

AC_Code

#include
using namespace std;
using ll = long long;
ll dp[50][1000];//dp[i][j]表示前i条街道，总共建造j个房屋的方案数
ll mod = 1e9 + 7;
int n, m, k;
int main() {
	cin >> n >> m >> k;
	for (int i = 0; i  n >> k;
	dp[0] = 1;//初始化
	for (int i = 1; i  n >> x;
	for (int i = 1; i > a[i];
	dp[0][0] = 1;//初始化
	for (int i = 1; i  k)return 0;
	if (dt[x][y] == '#')return 0;
	if (x == n && y == m)return 1;
	if (dp[x][y][d][step])return dp[x][y][d][step];
	int res = 0;
	for (int i = 0; i > n >> m >> k;
	for (int i = 1; i  dt[i][j];
	int ans = 0;
	if (dt[1][2] != '#')ans += dfs(1, 2, 0, 0);
	if (dt[2][1] != '#')ans += dfs(2, 1, 1, 0);
	cout  
表示a[i]要插入到不同的子序列后面的情况。
 
时间复杂度为O(n^2)，LIS还有一种利用二分实现的O(nlogn)时间复杂度的模型。
 
 
例题6.蓝桥勇士
 
 
AC_Code
 
#include
using namespace std;
int a[1003],dp[1003];
int main() {
	int n; cin >> n;
	for (int i = 1; i > a[i];
	for (int i = 1; i  a[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int ans = 0;
	for (int i = 1; i  n;
	for (int i = 1; i > t[i];
		dpl[i] = dpr[i] = 1;//初始化
	}
	//正向最长上升子序列
	for (int i = 1; i  t[j])
				dpl[i] = max(dpl[i], dpl[j] + 1);
	
	//反向最长上升子序列
	for (int i = n; i >= 1; --i) 
		for (int j = n; j > i; --j) 
			if (t[i] > t[j])
				dpr[i] = max(dpr[i], dpr[j] + 1);
	int ans = 0;
	for (int i = 1; i  n >> m;
	for (int i = 1; i > a[i];
	for (int i = 1; i > b[i];
	for (int i = 1; i > m;
	for (int i = 1; i > a[i];
	for (int i = 1; i > b[i];
	//--------此处求最长公共子序列长度--------
	for (int i = 1; i