动态规划

对于一个可以用动态规划实现的题目来说我们需要有以下步骤：
1.将原来划分为若干个阶段，每个阶段对应若干个子问题，提取子问题的特征（称为状态）
2.找到每个状态下可能得决策或者是各个状态的转移方式（就是寻找状态转移方程式）
3.按顺序求解每个阶段问题

基础动态规划问题

最长公共子序列

给定一个长度为n的序列a和一个长度为m的序列b，求出一个最长的序列，使得该序列既是A的子序列，也是B的子序列。
1.我们首先寻找这个问题的状态，dp[i][j]就表示序列a的前i个与序列b的前j个的最长公共子序列
2.我们尝试推导状态转移方程式，我们发现当a[i]=b[j]时，我们可以直接可以放在最长公共子序列的末尾，但当不等于时，我们可以选择跳过a[i]或者b[j]，此时我们就可以得出状态转移方程式了。
$$\{\begin{array}{ll}dp[i][j]=dp[i-1][j-1]+1& \text{ if }a[i]=b[j]\\ dp[i][j]=max(dp[i-1][j],dp[i][j-1]& \text{ if }a[i]\ne b[j]\end{array}$$此题的时间复杂度为O(nm)

string a,b;
int n,m,dp[N][N];
int solve(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
}

最长不下降子序列

给定一个长度为n的序列a，求出一个最长的a的子序列，满足该子序列的后一个元素不小于前一个元素。

算法一

用a数组表示原数组，dp[i]表示前i个数的最长不下降子序列。那么我们就可以遍历第1-i-1个数，如果第j个数不大于它就使dp[i]=dp[j]+1，遍历寻找dp[i]的最大值，此时我们可以得到状态转移方程式。
$$dp[i]=ma{x}_{j<i,a[j]<=a[i]}(dp[j]+1)$$这种解法的时间复杂度为O(n^2)

int n,a[N],dp[N];
int solve(){
    int ans=1;
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
            ans=max(ans,dp[i]);
        }
    }
    return ans;
}

算法二

我们发现刚刚的算法是将状态(j,l-1)在合法的前提下转移到(i,l)。所以我们只用设法找到(i,l)使l最大的合法的(i,l)就可以求得最长不下降子序列了。
我们设原数组为a，dp[i]表示所有长度为i的最长不下降子序列的末尾元素的最小值，len表示子序列的长度，所以我们发现当考虑元素a[i]时，若dp[len]小于等于a[i]，直接将它插入dp数组的末尾，如果dp[len]大于a[i]，我们就可以在dp数组中寻找第一个大于它的元素，然后用a[i]替换。
若直接用暴力查询，那么此题的时间复杂度仍然是O(n^2)，但我们发现dp数组是单调的，所以我们可以用二分查找将时间复杂度优化至O(nlogn)。

int n,a[N],dp[N];
int solve(){
    int len=1;
    dp[len]=a[1];
    for(int i=2;i<=n;i++){
        //a[i]>=dp[len]<-->a[i]<dp[len]，因此使用upper_bound
        if(a[i]>=dp[len]) dp[++len]=a[i];
        else dp[upper_bound(dp+1,dp+1+len,a[i])-dp]=a[i];
    }
    return len;
}

区间DP

对于区间DP我们是将问题分为左右两个部分，最后合并两个部分的最优值得到全局的最优值。
例题：在一个环上有n个数，进行n-1次合并操作每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。
我们先考虑在链的情况,写出状态转移方程。
$$dp[i][j]=max(dp[i][k]+dp[k+1][j]+\sum _{r=i}^j{a}_r)$$
其中求和部分不难发现可以使用前缀和优化。
因为我们要先知道dp[i][k]和dp[k+1][j]的值，因为当中dp[i][k]与dp[k+1][j]中包含的元素数量都小于dp[i][j]，所以我们可以使用len=j-i+1作为一个阶段确保我们可以知道前面我们要求的值。
对于一个环，我们可以将数组复制，放在原数组的后面，要使在新的数组取到的长度不超过原数组的长度。

for(int len=2;len<=n;len++){
    for(int l=1;l+len<=2*n){
        int r=l+len-1;
        for(int k=l+1;k<r;k++) dp[l][r]=max(dp[l][k]+dp[k+1][r],dp[l][r]);
        dp[l][r]+=s[r]-s[l-1];//前缀和优化
    }
}

背包DP

01背包问题

首先考虑最为简单入门的01背包问题。
有n个物品和一个容量为W的背包，每个物品有重量Wi和价值Vi两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
我们对于一个物品，我们有放入和不放入两个选择，我们定义dp[i][j]为对于前i个物品容量为j的背包能达到的最大总价值，所以我们可以列出状态转移方程式：
$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$$
但是我们发现对于一个二维数组来说可能会MLE（内存超限），所以我们考虑一维数组优化。
我们发现对dp[i]有影响的只有dp[i-1]，所以我们可以去掉第一维列出如下方程：
$$dp[j]=max(dp[j],dp[j-w[i]]+v[i])$$
我们在写01代码用一维数组优化时需要注意要从后往前更新，这样才会使得dp[j-[w[i]]的值未被更新，若从前往后遍历的话可能会出现一个物品被取多次的情况（事实上这样正是完全背包的解法）。

int n,wmax,w[N],v[N],dp[N];
void solve(){
    for(int i=1;i<=n;i++){//考虑每件物品
        for(int j=wmax;j>w[i];j++){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

完全背包问题

首先我们考虑朴素的做法，对于当前状态，枚举对每个物体选举多少个，得到状态转移方程式：
$$dp[i][j]=max(dp[i-1][j-k\times w[i]]+v[i]\times k)$$
但我们可以尝试进行优化，我们发现对于dp[i][j]只用考虑dp[i][j-w[i]]的值，因为dp[i][j-w[i]]已经是之前考虑的最佳取值，因此可以得到新的状态转移方程式：
$$dp[i][j]=max(dp[i-1][j-w[i]]+v[i])$$
与前面的01背包问题对比，我们也不难发现这次的更新是正向的，可以对于前面取过该物品得到的最佳取值继续进行选取。

int n,wmax,w[N],v[N],dp[N];
void solve(){
    for(int i=1;i<=n;i++){//考虑每件物品
        for(int j=w[i];j<=wmax;j++){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
}

多重背包

多重背包与01背包的区别就是，对于每个物品，01背包只能取1次，到那时多重背包可以取k次。
对于多重背包，我们可以想到一种十分朴素的办法，就是将k个同种物品转化为k个物品，每个物品只能选一次，用01背包进行处理，但是我们可以考虑一种二进制分组优化。假设一个物品有k件，将这个k进行拆分，让他成为n个数之和，使得所有小于等于k的所有数中，都能在那n个数中任选几个数使加和等于那个数的大小。
比如说：
$$8=1+2+4+1$$$$18=1+2+4+8+3$$
不难发现，我们先使2的n次幂从小到大相加(n>=0)，如果加上后超出原数那么我们就取要求的数与我们已选取的数的加和的差，不难发现这样的选取就可以满足取到所有小于等于k的取值。

struct node{
    int v,w;
}list[N];
int n,tot;
void changenum(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int v1,w1,num,c=1;
        cin>>v1>>w1>>num;
        while(num>c){
            num-=c;
            list[++tot].w=c*w1;
            list[tot].v=c*v1;
            c*=2;
        }
        list[++tot].w=num*w1;
        list[tot].v=num*v1;
    }
}

分组背包

有n件物品和一个大小为m的背包，第i个物品的价值为w[i]，体积为v[i]。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。
其实这个问题我们只用对组内进行一个01背包问题就可以解决了。我们可以用t[k][j]来表示第k组第j个的编号。

for(int k=1;k<=ts;k++){//遍历每个背包
    for(int i=wmax;i>0;i++){//遍历背包容量
        for(int j=1;j<=cnt[k];j++){//遍历每组背包的每个物品
            if(w[t[k][j]]<=i){//如果背包容量充足
                dp[i]=max(dp[i],dp[i-w[t[k][j]]]+v[t[k][j]]);
            }
        }
    }
}