AcWing 3428. 放苹果(dfs&dp两种做法
原题链接
简单
作者:
hanhyojoo
,
2024-02-18 17:07:12
,
所有人可见
,
阅读 31
dfs做法
#include<bits/stdc++.h>
using namespace std;
int m,n;
int lo[15];//每个位置的数字
int cnt;
void dfs(int u,int start)
{
if(u>n)
{ int sum=0;
bool flag=true;
for(int i=1;i<=n;i++)
{
sum+=lo[i];
}
if(sum==m)
cnt++;
return ;
}
for(int i=start;i<=m;i++)
{ lo[u]=i;
dfs(u+1,i);
lo[u]=0;
}
}
int main()
{
while(cin>>m>>n)//个数 位置
{
dfs(1,0);//上一个盘子的个数
cout<<cnt<<endl;
cnt=0;
}
return 0;
}
dp做法通过避免重复计算相同的子问题来提高效率。dp[m][n] 表示将 m 个苹果分配到 n 个盘子的方法数。递归的基本情况是当只有一个盘子或没有苹果时,只有一种分配方法。如果盘子数多于苹果数,那么问题可以简化为盘子数等于苹果数的情况。最后,通过递归计算两种情况的和来得到结果:至少一个盘子为空的情况和所有盘子都至少有一个苹果的情况。
#include<bits/stdc++.h>
using namespace std;
int m, n;
int dp[15][15]; // dp[i][j] 表示i个苹果放入j个盘子的分配方法数
int dfs(int m, int n) {
if (dp[m][n] != -1) return dp[m][n]; // 如果已经计算过,直接返回结果
if (n == 1 || m == 0) return 1; // 基本情况:如果只有一个盘子或没有苹果,只有一种分配方法
if (n > m) return dp[m][m] = dfs(m, m); // 如果盘子比苹果多,等同于苹果数等于盘子数的情况
return dp[m][n] = dfs(m, n - 1) + dfs(m - n, n); // 分为两种情况:至少一个盘子为空 + 所有盘子都有苹果
}
int main() {
memset(dp, -1, sizeof(dp)); // 初始化dp数组为-1
while (cin >> m >> n) {
cout << dfs(m, n) << endl;
}
return 0;
}