参考自アリ本(プログラミングコンテスト チャレンジブック)

01背包

个重值的物品，选总重的组合的最大价值。
（略）

最长公共子序列(LCS)

给两个字符串（s，t），求最长公共子序列。

int n,m;
char s[MAX_N],t[MAX_M]; // inputs

int dp[MAX_N + 1][MAX_M + 1]; // DP
void solve(){
    for(int i=0;i<n;i++){
        for(int j=0;j<0;j++){
            if(s[i]==y[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
        }
    }
    printf("%d\n",dp[n][m]);
}

最长上升子序列(LIS)

长数列。求最长上升子序列。

所有长度为的上升子列之中末尾元素最小值。
注意：最终算出来的数组并没有存这个LIS是什么，只能用来算LIS的长度。

int dp[MAXN];

void solve(){
    fill(dp,dp+n,INF);
    for(int i=0;i<n;i++){
        *lower_bound(dp,dp+n,a[i])=a[i];
    }
    printf("%d\n",lower_bound(dp,dp+n,INF)-dp);
}

多重部分和

个不同数字，每种个，能否选出正好和为的组合。

区间加到的的剩余，无法得到的话设为

// inputs
int dp[MAXK + 1];

void solve(){
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=k;j++){
            if(dp[j]>=0)
                dp[j]=m[i];
            else if(j<a[i] || dp[j-a[i]]<=0)
                dp[j]=-1;
            else
                dp[j]=dp[j-a[i]]-1;
        }
    }
    if(dp[k] >= 0) printf("Yes\n");
    else printf("No\n");
}

多重集组合数

个不同数字，每种个，从中取个的组合数。

从前钟物品中取个的组合数

int n,m;
int a[MAXN];

int dp[MAXN+1][MAXN+1];

void solve(){
    for(int i=0;i<=n;i++) dp[i][0]=1;
    for(int i=0;i<n;i++) 
    for(int j=1;j<=m;j++)
    if(j-1-a[i]>=0) dp[i+1][j]=dp[i+1][j-1]+dp[i][j]-dp[i][j-1-a[i]]; //Add MOD! otherwise it will <0
    else dp[i+1][j]=dp[i+1][j-1]+dp[i][j];
}

划分数&狭义划分数

把数m划分成不超过n个数的和，求划分组合。

定义
划分数：
狭义划分数：
定义狭义划分数为数m划分成正好n个数的和的组合数

这里我们有

且

同时

// inputs

int n,m;

int dp[MAXM+1][MAXN+1];

void solve(){
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(j-i>=0)
                dp[i][j]=dp[i-1][j]+dp[i][j-i];
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    printf("%d\n",dp[m][n]);
    
}