C++--りんごを入れる(ダイナミックプランニング)

タイトルの説明

 M        N       ，          ，           ？（ K  ）5，1，1 1，5，1       

  
           t（0 <= t <= 20）。           M N，     。1<=M，N<=10。

  
        M N，        K。

サンプル入力

2
6 3
7 2

サンプル出力

7
4

構想
n>m:必ずn-m個の皿が永遠に空いている場合は、リンゴを置く方法の数に影響を与えません.すなわちdp(m,n)=dp(m,m) n<=m:異なる放出法は2種類に分けることができる.

は、少なくとも1つの皿が空いている、すなわちdp(m,n)=dp(m,n-1)に相当する.動的計画または再帰の考え方によれば、dp(m,n-1)はすでにdp(m,n-2)の結果を含んでいるか、または次の層の再帰によって計算することができるので、これは最上位層のdp(m,n-1)を考慮するだけでよい.

すべての皿にはリンゴがあり、それぞれの場合の皿からリンゴを1つ取り除くことができることに相当し、異なる置き方の数(ここでは理解しにくい)、すなわちf(m,n)=f(m-n,n)に影響を及ぼさず、総置きリンゴの置き方の数は両者の和、すなわちdp(m,n)=dp(m,n-1)+dp(m-n,n)

に等しい.
境界:

かごの数が1の場合、すべてのリンゴは1つの皿に置かなければならない.方法数は1

である.

りんごの数が0の場合、方法数は1

である.
ACコード

#include
#include
using namespace std;
int main(){
     
    int n,apple_num,basket_num;
    cin>>n;
    while(n--){
     
        cin>>apple_num>>basket_num;
        int dp[apple_num+1][basket_num+1];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=basket_num;i++)  dp[0][i]=1;//  
        for(int i=0;i<=apple_num;i++)   dp[i][1]=1;//  
        for(int i=1;i<=apple_num;i++)
            for(int j=1;j<=basket_num;j++)
                if(i>=j)    dp[i][j]=dp[i][j-1]+dp[i-j][j];
                else        dp[i][j]=dp[i][i];
        cout<<dp[apple_num][basket_num]<<endl;
    }
    return 0;
}

OJアドレス
http://codeup.cn/problem.php?cid=100000632&pid=5