//数字三角形
/*
状态表示  f[i][j] 表示从(1,1)到(i,j)的最大路径和 
状态计算  f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
                      正上方     左上方 
*/
memset(f,-0x3f,sizeof f);

f[0][0]=0;  //初始化 
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=i;j++)
    {
        f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
        //        正上方       左上方   
    }
} 

//最长上升子序列模型

/*
状态表示 f[i]=k 表示以a[i]结尾的最长上升子序列长度为k
状态计算 f[i]=max(f[i],f[j]+1) j<i且a[i]>a[j] 
*/

int res=0;
for(int i=1;i<=n;i++)
{
    f[i]=1;
    for(int j=1;j<i;j++)
    {
        if(a[i]>a[j]) //可以拼接 
        {
        	f[i]=max(f[i],f[j]+1); //更新以a[i]结尾的最大值 
		}
    }
    res=max(res,f[i]); //更新以a[1]...a[i]结尾的最大值 
}

//公共子序列模型
/*
状态表示 f[i][j]=k 表示s1的前i个字符和s2的前j个字符的最长公共子序列长度 
f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+1->s1[i]==s2[j])
*/

cin>>s1+1;
cin>>s2+1;
n=strlen(s1+1);
m=strlen(s2+1);
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]); //不选第一个第i个字符或第二个的第j个字符 
        if(s1[i]==s2[j]) //相同，可以更新 
        {
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
}

//01背包
 //二维数组实现
 //代码实现1
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1010;
int f[N][M],v[N],w[N];
//状态表示 f[i][j]表示在前i个物品中选，体积不超过j的最大价值
//状态计算 1.不选 f[i-1][j]
//         2.选   f[i-1][j-v[i]]+w[i] 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) //获取物品体积和价值 
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++) //枚举物品 
    {
        for(int j=0;j<=V;j++) //枚举体积 
        {
        	f[i][j]=f[i-1][j];//不选当前物品
			if(j>=v[i])
			{
				f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); 
				//          原来的   选了的 里面的最大值	
			} 
        }
    }
    cout<<f[n][V];
    return 0;
}

一维费用背包实现
//代码实现2
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int f[M];
//状态表示 f[j]表示在前i个物品中选，体积不超过j的最大价值
//状态计算 1.不选 f[j]
//         2.选   [j-v[i]]+w[i] 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) //枚举物品 
    {
    	int v,w;
    	cin>>v>>w;
        for(int j=V;j>=v;j--) //枚举体积 
        {
        	f[j]=max(f[j],f[j-v]+w); 
			//     原来的   选了的 里面的最大值	
        }
    }
    cout<<f[V];
    return 0;
}

滚动数组实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1010;
int f[2][M],v[N],w[N];
//状态表示 f[i][j]表示在前i个物品中选，体积不超过j的最大价值
//状态计算 1.不选 f[i-1][j]
//         2.选   f[i-1][j-v[i]]+w[i] 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) //获取物品体积和价值 
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++) //枚举物品 
    {
        for(int j=0;j<=V;j++) //枚举体积 
        {
        	f[i&1][j]=f[i-1&1][j];//不选当前物品
			if(j>=v[i])
			{
				f[i&1][j]=max(f[i&1][j],f[i-1&1][j-v[i]]+w[i]); 
				//          原来的   选了的 里面的最大值	
			} 
        }
    }
    cout<<f[n&1][V];
    return 0;
}


//方案数

f[0]=1; //0的时候一种方案 
for(int i=1;i<=n;i++)
{
	int v;
	cin>>v; //获取当前物品 
	for(int j=V;j>=v;j--) //每个物品只能选一次，体积从大到小 
    {
		f[j]=f[j]+f[j-v];
	}
}
cout<<f[V];



//完全背包
//代码实现1
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1010;
int f[N][M],v[N],w[N];
//状态表示 f[i][j]表示在前i个物品中选，体积不超过j的最大价值
//状态计算 1.不选 f[i-1][j]
//         2.选   f[i-1][j-v[i]]+w[i] 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) //获取物品体积和价值 
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++) //枚举物品 
    {
        for(int j=0;j<=V;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]); 
				//          原来的   选了的 里面的最大值	
			} 
        }
    }
    cout<<f[n][V];
    return 0;
} 

一维数组实现
//代码实现2
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int f[M];
//状态表示 f[j]表示在前i个物品中选，体积不超过j的最大价值
//状态计算 1.不选 f[j]
//         2.选   [j-v[i]]+w[i] 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) //枚举物品 
    {
    	int v,w;
    	cin>>v>>w;
        for(int j=v;j<=V;j++) //枚举体积 
        {
        	f[j]=max(f[j],f[j-v]+w); 
			//     原来的   选了的 里面的最大值	
        }
    }
    cout<<f[V];
    return 0;
} 

//多重背包问题
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=110;
int f[N][M]; //f[i][j] 表示在前i种物品中选，体积不超过j的最大价值 
int v[N],w[N],s[N];
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i]>>s[i];
    }
    for(int i=1;i<=n;i++) //枚举物品 
    {
        for(int j=0;j<=V;j++) //枚举虚拟背包体积 
        {
            f[i][j]=f[i-1][j]; //不选当前物品 
            for(int k=1;k<=s[i];k++) //枚举选多少个当前类物品 
            {
                if(j>=k*v[i]) //可以选 
                {
                    f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
                }
            }
        }
    }
    cout<<f[n][V];
    return 0;
}

//区间动态规划
#include<bits/stdc++.h>
using namespace std;
const int N=310;
int s[N];
int f[N][N];
/*
状态表示 f[i][j]表示第i堆石子到第j堆石子合并的最小体力值 
*/
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]+=s[i-1];
    }
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) f[i][i]=0;
    for(int len=2;len<=n;len++) //枚举区间长度 
    {
        for(int i=1;i+len-1<=n;i++) //枚举左端点 
        {
            int j=i+len-1; 
           // f[i][j]=1e9;
            for(int k=i;k<j;k++) //枚举分界点 
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
} 
//扔鸡蛋问题
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=15;
int f[N][M];
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++) f[i][1]=i; //一层楼
        for(int i=1;i<=m;i++) f[1][i]=1; //一个鸡蛋
        for(int i=2;i<=n;i++)
        {
            for(int j=2;j<=m;j++)
            {
                f[i][j]=f[i][j-1]; //不用第j个鸡蛋
                for(int k=1;k<=i;k++)
                {
                    f[i][j]=min(f[i][j],max(f[k-1][j-1],f[i-k][j])+1);
                    //                      j个鸡蛋碎了   j个鸡蛋没有碎
                }
            }
        }
        cout<<f[n][m]<<endl;
    }
    return 0;
} 


#include<bits/stdc++.h>
using namespace std;
const int N=110,M=15;
int f[N][M]; //f[i][j]表示用了j个鸡蛋测i次的最大区间
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j]=f[i-1][j]+f[i-1][j-1]+1;
                //       没有碎    碎了
            }
            if(f[i][m]>=n)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;
}
//状态机模型
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N][2];
/*
f[i][0] 表示第i天没有股票的价值
f[i][1] 表示第i天有股票的价值 
*/
int w[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    memset(f,0xcf,sizeof f); //初始化无穷小 
    f[0][0]=0; //起点 
    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]); //第i-1天没有股票，卖了第i天的股票 
        f[i][1]=max(f[i-1][1],f[i-1][0]-w[i]); //第i天有股票，买了第i天的股票 
    }
    cout<<f[n][0];
    return 0;
} 


//拆数问题
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int f[N][N]; //f[i][j]表示将i分成j个数的方案数
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int m,n;
        cin>>m>>n;
        memset(f,0,sizeof 0);
        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;
    }
}

#include<bits/stdc++.h>
using namespace std;
int dfs(int x,int y)
{
	if(x==0) return 1;//没有苹果盘子都是空的
	if(y==0) return 0;//没有苹果，没有办法分
	if(y>x) //盘子数目大于苹果数目，最多使用x个盘子来放 
	{
		return dfs(x,x); 
	}
	return dfs(x-y,y)+dfs(x,y-1);
	//     没有空盘子,至少一个空盘子 
}
int main()
{
	int t,n,m;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		cout<<dfs(n,m)<<endl;	
	}	
	return 0;
}