北京大学の大学院受験の再試験は機に乗ります——リンゴを放します

1783 ワード
c/c++
M個の同じリンゴをN個の同じ皿の中に置いて、ある皿が空いていることを許して、何種類の異なる分け方がありますか?(Kで表す)5,1,1と1,5,1は同じ分法である.
説明を入力:
         M N，     。1<=M，N<=10。

出力の説明:
        M N，        K。

例1
入力
7 3

しゅつりょく
8

構想:ダイナミックプランニングの方法で、dp[i][j]でi個のリンゴをj個の皿に入れる方法の数を表し、数式を渡すと以下のようになる.
            dp[i][1] = 1; dp[1][j] = 1;//皿が1つしかないか、りんごが1つしかない方法の数は1です.
            dp[i][j] =dp[i][j-1] + dp[i-j][j];(i>j)/リンゴの数が皿の数より大きい場合、1すべての皿にリンゴを入れると、すべての皿にリンゴを1つ取り除く方法の数が変わらず、dp[i-j][j];2少なくとも1つの皿にりんごを入れない場合は、このりんごを入れない皿を取り除く方法は数が変わらず、dp[i][j-1]である.
             dp[i][j] = dp[i][j-1]; (i
             dp[i][j] = dp[i][j-1] + 1; (i==j)//りんごの数が皿の数に等しい場合、1すべての皿にりんごを入れると、すべての皿にりんごを1つ入れる方法の数は1です.2少なくとも1つの皿にりんごを入れない場合は、このりんごを入れない皿を取り除く方法は数が変わらず、dp[i][j-1]である.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int dp[15][15];

int main()
{
    int m, n;
    while(cin >> m >> n)
    {
        for(int i = 0; i <= m; i++)
        {
            dp[i][1] = 1;
        }
        for(int i = 0; i <= n; i++)
        {
            dp[1][i] = 1;
        }

        for(int j = 2; j <= n; j++)
        {
            for(int i = 1; i <= m; i++)
            {
                if(i > j) dp[i][j] = dp[i][j-1] + dp[i-j][j];
                else if(i < j) dp[i][j] = dp[i][j-1];
                else dp[i][j] = dp[i][j-1] + 1;
            }
        }

        cout << dp[m][n] << endl;
    }
}
css常用hackテクニック
React native基本紹介