【动态规划】POJ1664-放苹果

非常经典的划分数问题，即相当于把m个物体分成至多n组，求出分组总数。

【思路】当前状态dp[i][j]表示将i个物体分成至多j组的分组总数。对于当前状态，有以下两种情形：

（1）j组中有组为空，则这种情况下分组总数相当于将i个物体分成至多j-1组。即dp[i][j-1]。

（2）j组中没有组为空，则每一组至少有一个物体，这种情况下分组总数相当于将每一组取出一个物体后的分组数，再在每一组中添加一个物体。即dp[i-j][j]

值得注意的是，第二种情况的分组条件为i>=j。

所以，dp[i][j]=dp[i][j-1]+dp[i-j][j](i>=j)

　　　dp[i][j]=dp[i][j-1]　

初始时，将0个物体放入至多n组有1种情况，dp[0][n]=1；将m个物体放入1组有一种情况,dp[m][1]=1。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t;
int dp[25][25];//i个物体分为至多j组 

void distribute()
{
    scanf("%d%d",&m,&n);
    for (int i=0;i<=n;i++) dp[0][i]=1;
    for (int i=0;i<=m;i++) dp[i][1]=1;
    for (int i=1;i<=m;i++)
        for (int j=2;j<=n;j++)
        {
            if (i>=j) dp[i][j]=dp[i][j-1]+dp[i-j][j];
            else dp[i][j]=dp[i][j-1]; 
        }
    cout<<dp[m][n]<<endl;
    return; 
}

int main()
{
    scanf("%d",&t);
    for (int kase=0;kase<t;kase++) distribute();
    return 0;
}