华为机试 放苹果

题解：动态规划

采用dp[i][j] 表示 i个苹果放入j个盘子的不同分法数。
状态转移：
我们首先要明确一点，
j个苹果放入i个盘中中，总共有下列两种情况：

1. 盘子全部放满
2. 至少有一个盘子不放（为空）

一.当i>j 时，也就是苹果数多于盘子数时。

1）考虑盘子全部放满的情况，那么我们可以先每个盘子都放入一个苹果占位置。则剩下dp[i-j][j] 。等价于求解把i-j 个苹果放入j个盘子。
2）考虑至少有一个盘子不放的情况，也就相当于求解dp[i][j-1]。

由上我们可以得到i>j 时的状态转移方程：
dp[i][j] = dp[i-j][j] + dp[i][j-1]

二.当i<j 时，也就是苹果数少于盘子数时。
这时苹果不够，盘子肯定会有空的情况。等价于求解 把i个苹果放入i个盘子 ，即 dp[i][i]
得到状态转移方程：dp[i][j] = dp[i][i]
二.当i=j 时，也就是苹果数等于盘子数时。

同上分析，总共有下列两种情况：

1. 盘子全部放满
2. 至少有一个盘子不放（为空）

盘子全部放满只有一种情况（一一对应）。至少有一个盘子不放 对应于dp[i][j-1]。
对应的状态转移方程：
dp[i][j] = 1 + dp[i][j-1]

初始状态：

dp[0][x] 即苹果为0时，全部对应0种放法。
dp[1][x] 即苹果为1时，全部对应1种放法。

dp[x][0]即盘子为0时，全部对应0种放法。
dp[x][1]即盘子为1时，全部对应1种放法。

代码如下：

#include <iostream>
using namespace std;
#include<vector>

int main() {
    int m;
    int n;
    while(cin>>m>>n)
    {
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    
    for( int i=0 ;i<=n;i++)
    {   
        dp[0][i]=0;
        dp[1][i]=1;
    }
     
    for(int i=0;i<=m;i++)
    {   
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for(int i=2;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 if(i==j)
                dp[i][j] = dp[i][j-1]+1;
            else
                dp[i][j] = dp[i][i];
        }
    cout<<dp[m][n]<<endl;
    }
    return 0;
}