类型一：将n个苹果分成多份，最少可分0个，问所有的分配方案

参考例题： 鸣人影分身

大致思想：dp问题采用通用的dp分析法来思考，这个题的话
f(i,j)含义：将数字i分成j份的所有合法方案数
属性：个数
状态计算：一般dp问题划分集合的思路为寻找解决问题最后一个不同的点，这里的话我们以方案中的最后一位数字是否为0来划分状态。如果最后一位数字是0的话，那么f(i,j)=f(i,j-1);如果最后一位数字不为1的话，我们可以将每个方案中分配的数字都-1，这样做一个映射的话整体合法方案数是不变的，那么f(i,j)=f(i-j,j)

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=11;
int f[N][N],t,n,m;

int main()
{
    cin>>t;
    while(t--)
    {
        memset(f,0,sizeof(f));
        //m是能量总数，n是最多分配的个数
        cin>>m>>n;
        //设置边界
        //能量为0，分配0个的合法方案为1
        f[0][0]=1;//从语义理解，没能量，不分配，也算是一种合法的方案，
        for(int i=0;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]+=f[i][j-1];
                if(i>=j) f[i][j]+=f[i-j][j];
            }
        }
        cout<<f[m][n]<<endl;


    }
    return 0;
}

类型二：01背包类问题，选择+某种限制条件

参考例题： 糖果
思路：这种问题大致的意思都是从n件物品中选择若干件，然后再加上某一限定条件，例如这一题是要求模k结果为0，而往往这些限制条件都体现在状态方程的某一维上，例如本题，就采用其中一维表示模k的余数。并且个人感觉这种选择问题在划分集合时一般都按照最后一件物品选or不选来划分
状态方程：f(i,j)表示从前i件物品中选，并且物品总数量%k余数为j的最大值
属性：最大值
状态计算：1.若不选择第i件物品，那么f(i,j)=f(i-1,j)
2.选择第i件物品，那么 f(i,j)=f(i-1,(j-w[i])%k)+w[i];
第二种计算的推导：sum%k=j 那么 sum=nk+j -> sum-w[i]=nk+j-w[i]
两边同时%k, (sum-w[i])%k=(j-w[i])%k;

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=105;
int n,k,f[N][N],w[N];// w记录糖果的数目



int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>w[i];
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;//表示从0个糖果中选，模k为0，的最大值为0，语义是合理的

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<k;j++)
        {
            f[i][j]=max(f[i][j],f[i-1][j]);
            f[i][j]=max(f[i][j],f[i-1][(j+k-w[i]%k)%k]+w[i]);// 为了保证模后为正数，所以做了些操作

        }
    }
    cout<<f[n][0]<<endl;
    return 0;

}

类型三：寻找字符串中最长回文子序列的问题

大致意思就是：ACDECA, 则最长的回文子序列就是其中的ACCA,答案为4
参考例题： 密码脱落
思路：密码脱落这道题大致意思是，原先有一个，现在有一个残缺的字符串，问加多少个字符可以变成回文串，那么这实际上等价于现在这个字符串删除几个字符可以变成回文串，两个问题是等价的。所以就可以转化成求最长子回文序列问题，求出长度以后用字符串长度n-回文子序列长度=最少删除的个数

状态方程：f(l,r)表示字符串从l到r位置之间的最长子回文序列的长度的最大值
属性：最大值
状态计算：可以按照字符串l,r两端的情况来划分
1.子回文序列中包含字符串l,r两端的值, f(l,r)=f(l+1,r-1)+2;
2.子回文序列包含l，不包含r f(l,r)=f(l+1,r);(实际上这一计算包含了状态2，但因为是求最大值，所以无伤大雅，)
3.子回文序列不包含l，包含r f(l,r)=f(l,r-1)
4.子回文序列l,r两端都不包含 f(l,r)=f(l+1,r-1)

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int f[N][N];
char str[N];


int main()
{
    cin>>str;
    int n=strlen(str);

    //由于是区间dp，所以最外层循环长度
    for(int len=1;len<=n;len++)
    {
        for(int l=0;l+len-1<n;l++)
        {
            int r=l+len-1;//计算右边界
            if(len==1) f[l][r]=1;//特殊情况
            else
            {
                if(str[l]==str[r]) f[l][r]=f[l+1][r-1]+2;
                f[l][r]=max(f[l][r],f[l+1][r]);
                f[l][r]=max(f[l][r],f[l][r-1]);
                f[l][r]=max(f[l][r],f[l+1][r-1]);
            }
        }
    }
    cout<<n-f[0][n-1]<<endl;
    return 0;
}

类型四：最长上升子序列问题

参考例题1: 最长上升子序列
思路：本题要求的是给定一个数列，求其中严格单调递增的子序列长度最大是多少，可以将dp的状态看成是以每一个数字结尾的最长子序列的长度
状态方程：f[i]表示以第i个数字结尾的最长上升子序列的长度，这样的话就可以进行状态的转换了，如果在i之前的某个数字num[j]是小于num[i]
的话，那么f[i]=f[j]+1，即f[i]这个状态可以是 f[j]的长度+1，1即为num[i]本身这个数字的长度，所以状态计算就是f[i]=max(f[j]+1,f[i]) if(num[j]<num[i])

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=1000+5;
int num[N],f[N],n;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>num[i];

    for(int i=0;i<n;i++)
    {
        f[i]=1;//若没有比 num[i]小的，则它长度为1
        for(int j=0;j<i;j++)
        {
            if(num[j]<num[i])
            {
                f[i]=max(f[j]+1,f[i]);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=max(res,f[i]);
    }
    cout<<res<<endl;
    return 0;
}