题解 | #放苹果#
放苹果
http://www.nowcoder.com/practice/a2a1d0266629404fba582d416d84b6a0
先写递归，然后再用dp简化复杂度，这样思路更清晰
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 1024;
int dp[32][32];
//m个苹果，n个盘子
int ways(int m, int n) {
if (m == 0) {
dp[m][n] = 1;
return 1;
}
if (n == 0) {
dp[m][n] = 0;
return 0;
}
if (dp[m][n] != -1)return dp[m][n];
//核心递推
if (n > m) {
dp[m][n] = ways(m, m);
return dp[m][n];
}
else {
dp[m][n] = ways(m - n, n) + ways(m, n - 1);
return dp[m][n];
}
}
int main() {
int m, n;
while (cin >> m >> n) {
memset(dp, -1, sizeof(dp));
cout << ways(m, n) << endl;
}
return 0;
}
查看6道真题和解析
投递美团等公司6个岗位