题解 | #放苹果#

####这道题要注意边界条件，苹果和盘子那里的转移方程不太好理解，我尝试着解释一下，详情看代码

#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int m,n;
    while(cin>>m>>n){
        vector<vector<int>> v(m+1,vector<int>(n+1,0));//这里有0个苹果和0个盘子
        //的边界条件以及m个苹果n个盘子的情况，数组应该是m+1，n+1
        for(int i =0;i<m+1;i++){
            v[i][0]=0;//这里思考比如1个苹果放0个盘子，这种情况是没有的设为0
            if(i>=1)
            v[i][1]=1;//放一个盘子只有一种放法
        }
        for(int i =0;i<n+1;i++){
            v[0][i]=1;//这里要注意了，0个苹果放i个盘子应该设为1，为什么？下面再解
            //解释
            if(i>=1)
            v[1][i]=1;//1个苹果放i个盘子应该只有1种放法
        }
        int temp;
        for(int i =1;i<m+1;i++){
            for(int j =1;j<n+1;j++){
                if(i>=j)temp=v[i-j][j];//这里要非常详细的理解一下，苹果数量比盘
                //子大的情况，举个例子4个苹果3个盘子的放法实际上分为几个互斥的
                //的事件1、4个苹果3个盘子独有的放法（就是要用到3个盘子）2、4个
                //苹果2个盘子独有的放法，3、4个苹果1个盘子独有的放法。0个盘子
                //没有放法，这里用i-j其实就是要求j个盘子独有的放法，比如4个
                //苹果把3个盘子都用上的放法和（4-3）=1个苹果放3个盘子是一样的。
                //好了这里可以知道为什么前面0个苹果i个盘子要设为1了，因为
                //这里的苹果数和盘子数相等的情况（i==j)i个苹果对j个盘子的放法
                //只有一种，其实就是0个苹果j个盘子的放法。
                else temp=0;//i<j的时候，i个苹果放到j-1个盘子和i放到j个盘子一样
                v[i][j]=v[i][j-1]+temp;//这里总的放法要把互斥的加起来。
                
                
            }
        }
        
        cout<<v[m][n]<<endl;
    }
}