动态规划
概括
对于动态规划，我们主要从状态表示f[i,j]与状态计算公式入手，i表示选择范围，若i=5即表示从前5个物品中进行选则，j表示背包现有体积，若j=5，即表示背包体积为5的情况
1.状态表示：状态表示分为集合和属性两个部分。对于集合，我们可以形象的概括为许多个格子(所有表示且满足题目的所有条件)，每个格子即代表当前的状态；而属性，则是填在格子上的值，表示当前状态我们所需要的一种情况。
对于我们的数组而言，每一维都表示着一个状态，而数组中存放的数据就是我们数组所要计算的数据
2.状态转移：由前面的数据我们不难看出，我们的数组的每一维表示一个状态，而这个而最终数组上存放的数就是当前状态下我们要求的数据。
那么我们要这么得到这个数据呢？
这就需要我们对原本的数据进行转移。
所谓状态转移，其实就是当前状态如何由之前的状态得到，这些方法可能包含数学计算也可能包含选择语句，但整体上都是在用之前的状态求出我们需要的状态。
那么我们就会发现一个起始的问题，那就是我们会需要一个最初的状态，这个状态就是初始值，而对这个初始值进行赋值我们就称为状态的初始化。
动态规划一般分析顺序：
1.思考dp数组应都有哪些状态，这个状态的数量就是我们要写循环数量，是我们所有可能性的集合，这个维度的数目一般会在题目中和已知模板的嵌套中有所体现。如果一个题目存在多个模板的对应，很可能就有多个维度
2.思考dp数组每一格上都放什么，放的内容表示该状态下的什么数据：一般为 “ max，min，种类 ” 三种，这个一般就是题目中要求的数据，很容易就能发现。
3.思考一个普适的状态，如何经过其他状态转移过来，要寻找一个普适的方法
4.然后我们就可以开始代码化了，代码化一般包括以下几步
i ：dp数组初始化即对最开始的状态进行赋值
ii ：写循环，一般几维就是几层循环（维度可能不和dp数组的维度对应，但一般和循环数对应），状态的枚举一般都是在循环中直接枚举全部情况。
iii ：写状态转移，状态转移是如和通过前推后，所以存在两步：状态处理&&数据处理
状态处理：即如何查找哪些状态转移到该状态，一般是对下标上的数进行加减或者使用向量进行位移，有时还要通过选择语句进行特判（即存在多种不同的转移方式）
数据处理：即对上一个/堆状态进行怎样的一个操作才能得到该状态下的数据
PS:注意数据的初始化与特殊情况的存在性与取值
时间复杂度：dp问题的朴素做法的时间复杂度一般为O（状态数量x转移量）
ps：转移量：算出该状态上的数据所需要的行数
背包问题
01背包问题
题目
思想
f[i,j]中i表示放入物品的数量，j表示我们假定的背包当前容量
状态转移方程f[i,j]表示当前的最大情况，我们将集合划分为装i与不装i然后在二者中求最大值，这就是我们状态转移方程的由来。
状态转移方程的构建：将集合划分，如何前推后，要求的是什么
问题
问题1.为什么要假定背包容量
问题2.为什么不一开始就放入所有物品
答：对于dp问题，我们在处理问题时只能一层一层的处理，所以只能从最底层开始向更高层慢慢推进。
问题3.为什么会有不装满体积的情况
答，可能所有物品在选中后体积和凑不出背包总体积，也可能存在耗得体积少但是总价值高的情况，在层层推进中，我们的max函数就起到了求最大值的作用
代码实现
#include <iostream>
using namespace std;
const int N=1010; //多开出10个空间
int f[N][N],v[N],w[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //让物品的下标与下方循环对应，第0号代表没有，即不放物品
//整个循环先对体积遍历再对数量遍历
for(int i=1;i<=n;i++){ //由于放入物品为0时全部都是0，所以不考虑该层循环
for(int j=0;j<=m;j++){ //此从1开始也可见ac，原因在于当背包体积为0时装不下任何物体，所以当前背包总价值同样还是0，所以i=0时亦可不进行操作
if(j<v[i]) f[i][j]=f[i-1][j]; //当遍历过程中体积放不下第i个物品时，当前状态与前一状态无差
else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]); //当可以放下时，我们再能放i和不放i两种情况中选择最大值放入当前格子
}
}
cout<<f[n][m]; //f[n,m]即为最后一个方格，该格子囊括了前方所有的状况
}一维优化———滚动数组
对于原本的题目，我们不难发现，每一层的数据均只会用到该层的上一层，在这种情况下，我们便可以使用滚动数组来对原题目进行优化
对于滚动数组优化，存在两种形式，即j逆序遍历与j正序遍历，二者使用哪一种情况，主要取决于我们在朴素算法中更新状态时使用的数据，应先确定我们使用的数据是否需要更新，如果不需要，再看我们将维度去掉后使用的数据是否仍然是未更新的状态，若不是，则应采用不会使后续使用数据被更新的遍历方式，反之，则使用会令其更新的方式
代码实现
#include <iostream>
using namespace std;
const int N=1010;
int f[N]; //优化为一维数组，数组内下标放j
int v[N],w[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){ //虽然在数组中删掉了i，但是整体思想不变，我们仍然要对i进行遍历，来完成每一轮
for(int j=m;j>=v[i];j--){ //由朴素算法我们可以看出只有当j>=v[i]时数组才会发生更新，不然会始终保留上一轮数据，所以我们直接将循环的条件改为j>=v[i] 然后执行改变操作即可
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
}ps：
对于该题，我们每回使用的数据为上一层的j-v[i]，首先上一层，表示我们应该使用不让数据更新的遍历方式，其次j-v[i]，表示我们每回使用的数据都在左侧，所以从右向左遍历（更新）不会是后续数据被更新从而影响dp执行。
完全背包问题
题目
简介：想对01背包问题，完全背包问题中的所有物品均可使用无限次
思路
代码实现
#include <iostream>
using namespace std;
const N=1010;
int v[N] w[N];
int f[N][N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); //核心代码，当k=0时，f[i][j]=0 f[i-1][j-k*v[i]]+k*w[i]=f[i-1][j],即将f[i][j]更新为f[i-1][j]，即完成了对f[i][j]的初始化
}
}
}
cout<<f[n][m];
}第一次优化———减小循环次数
由上图我们不难看出f[i,j-v]与f[i,j]的后半部分只差了一个w，所以我们可以用f[i,j-v]来替代掉f[i,j]的后半部分
代码实现
#include <iostream>
using namespace std;
const int N=1010;
int f[N][N];
int w[N],v[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j]; //每次都要先进行初始化操作
if(j>=v[i]) f[i][j]= max(f[i][j],f[i][j-v[i]]+w[i]); //接着在进行大小的比较，此处全为i，所以均为本层数据，故需要从小到大遍历
}
}
cout<<f[n][m];
}第二次优化———滚动数组
由于完全背包问题的状态表示方程仍然满足鼓动数组的使用请况，所以我们使用滚动数组来对其进行优化,滚动数组的优化操作实现只是简单的对于朴素做法删掉一维后考虑是否前后等价即可。
代码实现
#include <iostream>
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
}注意： 完全背包问题这里在取max时本身就是对本层进行比较，所以循环仍然从小到大遍历
最长上升自序列问题
**总结：**对于动态规划问题，dp数组的长度与循环次数并无关系，循环次数主要取决于集合的划分，循环需要在每一次运行中均可以使集合的划分情况全部被执行到
代码实现
#include <iostream>
using namespace std;
const int N=1010;
int dp[N],str[N],g[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>str[i];
for(int i=1;i<=n;i++){
dp[i]=1; //最短子序列即它本身，长度为1
for(int j=1;j<i;j++){
if(str[j]<str[i]) { //如果i前面的数字小于j，i才可以接上他的子序列。
if(dp[j]+1>dp[i])g[i]=j; //g数组存放的为该下标对应的数字由谁转移而来，由于循环的存在，可以保证该位置最后存放的为最大的子序列所对应的前一个转移数字
dp[i]=max(dp[i],dp[j]+1); //但是i不一定要接上j的子序列，只有接上后为最大子序列，我们才让他接上
}
}
}
int res=dp[1],k=1;
for(int i=2;i<=n;i++){ //遍历查找最长子序列
if(dp[i]>res) k=i;
res=max(res,dp[i]); //不一定原数字串的最后一个数所对应的子序列就是最长子序列（比如最后一个数是1）
}
cout<<res<<endl;
while(k!=0){
cout<<str[k]<<' ';
k=g[k];
}
}最长公共子序列问题
#include <iostream>
using namespace std;
const int N=1010;
int dp[N][N];
char str1[N],str2[N];
int main(){
int n,m;
cin>>n>>m；
for(int i=1;i<=n;i++) cin>>str1[i];
for(int i=1;i<=m;i++) cin>>str2[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(str1[i]==str2[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<dp[n][m];
}区间dp
**思想：**区间dp问题的描述通常为间几个部分进行和并，这时我们就会使用区间dp的做法来解决这类问题。区间dp的循环枚举的往往是区间长度，即先将由两个数构成的小区间合并，再将由两个小区间构成的大区间合并以此类推，进而完成对整个区间的合并
例题：石子合并
设有 N堆石子排成一排，其编号为 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2、3堆，则代价为7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N。
第二行 N个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
代码实现
#include <iostream>
using namespace std;
const int N=310;
int dp[N][N],s[N];
int INF=1e9;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>s[i];
s[i]+=s[i-1]; //求前缀和数组，根据前缀和数组的性质，可以求得每一个位置的数字及每个长度的区间
}
for(int len=1;len<=n;len++){ //从小到大枚举所有区间
for(int l=1;l+len<=n;l++){
int r=l+len; //枚举左右区间
dp[l][r]=INF; //将每一个位置先初始化为最大，便于后方第一轮求最小
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]-s[l-1]+s[r]) //因为len从小到大遍历，所以每个位置此时均为最小（起始时其他位置均为0）。后面的前缀和表示最后两堆相加，最后俩堆相加的和一定为该区间所有石子重量的和
}
}
}
cout<<dp[1][n];
}状态压缩dp
简介
状态压缩dp是基于位运算进行操作的一类dp，通过一个整数二进制形式每一位的01来表示该情况当前的状态
位运算基本操作
一般基础的状压就是将一行的状态压成一个数，这个数的二进制形式反映了这一行的情况。由于使用二进制数来保存被压缩的状态，所以要用到神奇的二进制位运算操作，将一个十进制数转成二进制进行位运算操作再转回十进制数。
基本位运算包括：
- 按位与&（有0为0，其实就是且）
- 按位或|（有1为1，其实就是或）
- 按位取反~（注意负数补码的符号，最前面的第一位是1）
- 异或^（相同为0，不同为1）
- 左移<<
- 右移>>
最最重要的一点：
位反（~ ) > 算术（加减乘除） > 位左移、位右移 > 关系运算（大于 小于 等于 不等于）> 位与 > 位或 > 位异或 > 逻辑运算所以一般位运算最好打括号。
树状dp
简介：
所谓树状dp，即题目的描述为一个树状的图形，且父节点状态可以用子节点状态来进行转移（或逆向），这一类dp我们通常称之为树状dp，对于树状dp，我们常常要结合之前学的图论与搜索的知识，对其进行遍历
经典例题————没有上司的舞会
题意理解
我们不难看出，题目中上司和下属的关系就是树的关系，所求为快乐指数综合的max值。
对于一个以i为根节点的树，其状态存在两种情况，即选i与不选i。所以我们的答案一定是两种状态中的一个。由此我们便可以得到此题的dp数组：dp[N] [2]
1.选 i :如果我们选了i这个节点，我们首先就应该将**dp[i] [1]初始化为其本身的幸福值。对于其子节点，则一定不可以选，所以其幸福值直接加上dp[j] [0]**即可（j表示i的任意子节点，1表示选用该节点后该节点幸福值的最大值，0表示不用该节点后该节点幸福值的最大值）
2.不选i：如果我们不选这个节点，那么我们的**dp[i] [0]**就应该初始化为0。对于其子节点，我们就一定选吗？答案肯定为不是，因为我们无法确定其子节点选与不选究竟谁大，所以我们就应该选择大的那一个，
代码实现
#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;
int n;
int h[N],e[N],ne[N],idx;
int dp[N][2];
bool has_father[N];
int happy[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int root){
dp[root][1]=happy[root];
for(int i=h[root];i!=-1;i=ne[i]){
int j=e[i];
dfs(j); //由于递归的本质是调用栈，而栈的特点即是触底再运行·，所以我们会一直运行到叶子姐节点处再运行后面的状态转移方程
dp[root][0]+=max(dp[j][0],dp[j][1]);
dp[root][1]+=dp[j][0];
}
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++) cin>>happy[i];
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
add(b,a);
has_father[a]=true;
}
int root=1;
while(has_father[root]) root++;
dfs(root);
cout<<max(dp[root][0],dp[root][1]);
}记忆化搜索————♥递归与DP的禁忌之恋♥
简介
对于动态规划，我们不难发现其基本思想就是对于一个问题，我们寻找其子问题，通过子问题最优解得到本题答案
动态规划不同于贪心算法，因为贪心算法是从局部最优来解决问题，而动态规划是全局最优的。用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策，而是必须等待子问题得到了最优解之后才对当下的情况做出决策，所以往往动态规划都可以用 一个或多个递归式来描述。而贪心算法却是先做出一个决策，然后在去解决子问题。这就是贪心和动态规划的不同。
一般遇到一个动态规划类型的问题，都要确定我们的子问题的最优解究竟是是什么，以及如何才能让子问题做到不重不漏，这两个是动态规划最大的特征，然后就是得出动态规划的状态转移方程。然后就是自底向上的求解问题，先将最小规模的子问题的最优解求出，并将其用dp数组记录下来，到后来遇到同样的问题的时候就可以直接之前的答案得出，最后就是通过一步一步的迭代得出问题的答案了。
记忆化搜索（Memory Search），其实就是用递归函数来对dp进行实现，核心语句就是那两部分关键的语句块啦。
1.函数一开始的判断出口：if(搜索过) return 数组中的值。因为这里涉及到是否搜索过，所以一般将数组初始化为-1，详情见那道经典的滑雪题目：链接稍后送上。那道滑雪题，也可以用dp解，他俩的区别和解题的不同一会博客中也会有提到。
2.函数的递归前进语句：return fib[i]=fib[i-1]+fib[i-2];（没有具体的例子实在不好说了，所以这里用fib数列来做演示）。
这样就做到了数组的每个值只计算了一次，不会有多余的时间消耗。
而记忆化搜索相对于DP的优势就在于，记忆化搜索可以略去DP复杂的排序操作（所有的dp必须按照特定的顺序进行求解才能得到最终答案，而所谓的特定顺序，就是从最小子问题一步步向大问题推进，所以我们不免会面对三个问题，如何找到最小子问题？谁是最小子问题的父问题？如何才能得到一个通用的循环顺序？）。将所有的问题交给栈和递归取去维护，这便是MS相对DP最大的优势！
经典例题
如果采用常规DP，我们会发现这个题我们很难找到一个合适的循环顺序，这时我们便采用记忆化搜索来进行实现
代码实现
#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int map[N][N];
int dp[N][N];
int n,m;
int ty[]={1,0,-1,0},tx[]={0,1,0,-1};
int ms(int y,int x){ //传入的参数就是我们本次递归过程中要更新的dp的下标
if(dp[y][x]!=-1) return dp[y][x]; //如果dp[y][x]已经求解出来了，那么就将dp[y][x]的值返回过去
//这里便是ms最重要的两步之一：判断边界并返回数值
dp[y][x]=1; //即使四个方向都去不了，该位置的路线长也有1
for(int i=0;i<4;i++){
int dx=x+tx[i],dy=y+ty[i]; //遍历四个方向
if(map[dy][dx]!=-1&&map[y][x]>map[dy][dx]){ //判断死否合法以及可不可以到达
dp[y][x]=max(dp[y][x],1+ms(dy,dx)); //这里便是ms最重要的两步之一：状态转移方程
//该处的值始终是最大，每次用可达的方向的路线长+1去更新
//此时我们就可以发现ms最大的优势，先循环输入所有情况到函数中，如果之前已经求过，那么直接返回，如果没求过，我们便会进入到状态转移方程，而进入状态转移方程后，我们还是会面对那个当前输入的数据求没求解过的问题，若求解过，就返回，没求过，就去求。由此可见ms会自己在需要的时候去求问题的解，由大问题自动向下寻找子问题，而不需要我们提前设计好循环，让其在循环中求解。
}
}
return dp[y][x];
}
int main(){
cin>>n>>m;
memset(map,-1,sizeof map); //对图用-1初始化可以使代码判断边界时更加简单
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
}
int ans=0; //用于记录答案
memset(dp,-1,sizeof dp); //ms一般使用-1对dp数组进行初始化，表示该位置当前未计算过
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,ms(i,j)); //输入我们每次像要求的最终数据，此处在更新最大值
}
}
cout<<ans;
}