放苹果组合问题--DP实现

放苹果组合问题--DP实现

初始状态转移矩阵dp[n][m],dp[i][j]表示i个盘子放j个苹果的放法；

状态转移方程为

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

int putapples(int m, int n){
    if(!(m >=0 && m <=10)) return -1;
    if(!(n >=1 && n <=10)) return -1;
    if(1 == n) return 1;
    if(m <= 1) return 1;
    if(m <= n) n = m;
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    dp[1] = vector<int>(m+1, 1);
    for(int i = 1; i <= n; ++i) dp[i][0] = dp[i][1] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j  = 2; j <= m; ++j){
            dp[i][j] = dp[i-1][j] + (j-i < 0 ? 0:dp[i][j-i]);    
        }
    }
    return dp[n][m];
}

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