动态规划初步
**找出动态转换方程！**
抄来的：
> 动态规划求出的是最优状态，所以必然也是针对状态的操作，而状态自然可以出现在最优解中，也可以不出现——这便是决策的特性（布尔性）。
其次，由于每个状态均可以由之前的状态演变形成，所以动态规划有可推导性，但同时，动态规划也有无后效性，即每个当前状态会且仅会决策出下一状态，而不直接对未来的所有状态负责，可以浅显的理解为——
Future never has to do with past time ,but present does.
现在决定未来，未来与过去无关。
**用DP解决问题必要的条件：**
1， 可以划分方案；
2， 符合最优解原理；
3， 具有无后效性；
## LIS（最长上升子序列）：
```c
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
int ans;
#define MAXN 2111
int f[MAXN];
int a[MAXN];
int n;
int main() {
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++) {
f[i] = 1;//（初始化边界） 不然j不循环时，f[1] = 0 本来他自己是可以组成一个LIS的
for(int j = 1; j <= i - 1; j++) { //注意！ j 在 i 前面
if(a[i] > a[j]) //枚举出i前面的最长上升子序列
f[i] = max(f[i] , f[j] + 1);//因为是枚举，可能出现这个情况：
/* 3 4 5 4 6
i = 5 时 f【i】 ={2 ， j = 1 时
3 ， j = 2 时
4 ， j = 3 时
3 ， j = 4 时
f[4]并不是大于f[3]
*/
}
}
for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
printf("%d\n", ans);//输出的是 n 之前的最短上升子序列
return 0;
}
```
## LCS(最长公共子序列):
大佬博客：
https://blog.csdn.net/hrn1216/article/details/51534607
还有字串
给出n,m的两个排列P1和P2，求它们的最长公共子序列。
```c
#include <cstdio>
#include <algorithm>
#define MAXN 1000
#define MAXM 1000
using namespace std;
int a[MAXN],b[MAXM];
int n,m;
int f[MAXN][MAXM];
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= m; i++) scanf("%d",&b[i]);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
f[i][j] = max(f[i][j - 1] , f[i - 1][j]) ;
if(a[i] = a[j]) f[i][j] = min(f[i - 1][j - 1] + 1 , f[i][j]) ;
else f[i][j] = min(f[i - 1][j - 1] , f[i][j]);
}
}
printf("%d",f[n][m]);
}
```
## 矩阵里的DP：
/*题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。
输入输出格式
输入格式：
输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.
输出格式：
一个整数，最大正方形的边长
输入输出样例
输入样例#1：
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
输出样例#1：
2
注： f[i][j]表示以（i，j）为右下角的正方形的最长边
**f[i][j] = min (f[i][j-1],f[i-1][j],f[i-1][j-1])+1**
**f[i][j] 受且仅受它左，上，左上方代码的限制 因为加上（i，J）自己后，边就增长了1**
```c
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans;
int f[111][111],a[111][111];
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d",&a[i][j]);
if(1 == a[i][j]) f[i][j] = 1;//初始化，每个点都可以作为一个长为1的正方形
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(f[i][j] == 1) f[i][j] = min(f[i - 1][j] , min(f[i][j - 1] , f[i - 1][j - 1])) + 1;//找到一个合法的点之后，才能运用状态转换方程
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
ans = max(ans , f[i][j]);//枚举出最大的
}
}
printf("%d",ans);
}
```
## 区间DP：luogu ：P1220
```c
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 555
int n,c;
int dp[MAX][MAX][2];
//dp[i][j][0/1]表示老张关完i ~~ j的灯时所在的位置
int sum[MAX]/*前缀和：用来计算功率*/,a[MAX],b[MAX];/*a是位置，b是功率*/
int min(int a, int b) {
return a >= b ? b : a;//提高效率
}
int main() {
scanf("%d%d",&n,&c);
memset(dp,88,sizeof(dp));
for(int i = 1; i <= n; i++) {
scanf("%d%d",&a[i],&b[i]);
sum[i] =sum[i - 1] + b[i];
}
// printf("%d",sum[2]);
dp[c][c][0] = dp[c][c][1] = 0;//老张直接将自己所在的灯关掉，无时间，所以无功
for(int l = 2; l <= n; l++) {// 枚举现在的灯
for(int i = 1; i + l - 1 <= n; i++) { //不能越界
int j = i + l - 1;// 时间∨
dp[i][j][0] = min(dp[i + 1][j][0] + (a[i + 1] - a[i]) * (sum[n] - sum[j] + sum[i]),//包括了i这一点的电能，因为走过来的过程中灯i也会耗电
dp[i + 1][j][1] + (a[j] - a[i]) * (sum[n] - sum[j] + sum[i])) ;
dp[i][j][1] = min(dp[i][j - 1][1] + (a[j] - a[j - 1]) * (sum[n] - sum[j - 1] + sum[i - 1]),//已经关了[i,j - 1] 注意：i关了，j还没关 所以j会耗电，i不会
dp[i][j - 1][0] + (a[j] - a[i]) * (sum[n] - sum[j - 1] + sum[i - 1]));
//dp[i][j][0] ---- i + 1 dp[i][j][1] ---- j - 1 他们对应的都是上一个状态
}
}
int ans = min(dp[1][n][0] , dp[1][n][1]);
printf("%d",ans);
}
```
## 背包：
**学习博客**
https://www.cnblogs.com/fengziwei/p/7750849.html
### 0-1背包：
```c
#include<cstdio>
#include<algorithm>
using namespace std;
/*
n 个 物品 每件物品的体积为 v[] 和 价值 w[] 有一个大小为 m的背包 问 选完后的最大价值
*/
/*f[i][j] 表示 选了 i 个物品 背包内的物品体积为 j时的最优价值*/
int main() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];//不选的情况 //不能直接写max(f[i - 1][j] , f[i - 1][j - v[i]] + w[i]) 因为不知道能不能放
if(j >= v[i]) //如果可以放
f[i][j] = max(f[i][j] , f[i - 1][j - v[i]] + w[i]);//就先比较一下放与不放的价值
}
}
//一维简化
/*f[j]表示 花费为j时的最大价值*/
for(int i = 1; i <= n; i++) {
for(int j = m; j >= v[i]; j--) {// j >= v[i]是为了看放入第 i 个物品之前，体积为j - v[i]时的最优价值
f[j] = max(f[j] , f[j - v[i]] + w[j]);
}
}
}
```
### 完全背包
即每种物品的个数是无限的
核心代码：
```c
for(int i=1;i<=n;i++)
for(int j=w[i];j<=V;j++)//注意为顺序
f[j]=max(f[j],f[j-w[i]]+v[i]);
```
顺序的原因：
