题解 | #放苹果#

#include"iostream" #include"algorithm" #include"cstring" #include"vector" #include"map" #include"set" #include"cmath" using namespace std;

/* 典型的动态规划的题解：f(m,n) 表示 m个苹果放到n个盘子里面的总可能数； 1、当至少有一个空盘子时：f(m,n) = f(m,n-1); // 在递归的调用过程中会调用到f(m,n-k) k = 2,3,4... 2.当所有盘子都有苹果时：f(m,n) = f(m-n,n); 因此最终的最次数应是f(m,n) = f(m-n,n) + f(m,n-1); */
const int MAX = 12; int dp[MAX][MAX]; // 动态规划做法； int main() { int n , m ; while(cin>>m>>n) //m表示苹果，n表示盘子； { memset(dp,0,sizeof(dp)); // 头函数是 cstring for(int i = 0 ; i <= m ;i++ ) dp[i][1] = 1; // 当只有一个盘子时，只有一种摆法； for(int j = 0 ; j <= n ; j++) dp[0][j] = 1 ;//dp[1][j] = 1; // 当没有苹果或者只有一个苹果时，只有一种摆法；

    for(int i = 1; i <= m ;i++ )
    {
        for(int j = 1 ; j <= n ; j++)
            if(i < j)    //    当苹果数小于盘子数时，j-i个盘子必然时空的，所以在i个盘子里面放i个苹果；
                dp[i][j] = dp[i][i];
            else
                dp[i][j] = dp[i-j][j]+dp[i][j-1];
    }
    cout<<dp[m][n]<<endl;
}

return 0;

}

/* 递归做法：DFS;

int f(int m, int n) { if(m < 0) // 当没有苹果时，也算是一种摆法； return 0; if(m == 1 || n == 1) return 1; return f(m-n,n) + f(m,n-1); // f(m,n-1)的递归调用过程中会调用到f(m,n-k) k = 2,3,4... }

int main() { int n , m ; while(cin>>m>>n) { cout<<f(m,n)<<endl; }

return 0;

} */