AcWing 3428. 放苹果(dp)
原题链接
中等
作者:
orange0912
,
2021-05-15 11:19:18
,
所有人可见
,
阅读 1917
dp 做法 从下面暴力递归而来
/*
f(n,m) : 求n个盘子装m个苹果的方案数
找 比 n 小1的规模的方案数,来推出 n规模的方案数
如果找到了 n-1个盘子装 m个苹果的方案数,可能可以推 出n个盘子装m个苹果的方案数
1) M苹果<N 盘子 推出N-M个盘子不装苹果,拿掉这些盘子不影响方案数,剩下
f(n,m)=f( m ,m)
2) M苹果 >= N 盘子 f(n,m)=f(n-1,m)+f( n,m-n )
分2种情况
(1) 一个盘子不装苹果 f(n,m)=f(n-1,m)
(2) 第(1)种的相反情况 可以用 a&&b&&c&&d&&0 的相反情况 也就是 abcd都为1
一个条件为0的相反条件就是 所有条件必须都为1
每个盘子至少放1个球
每个盘子放1个球,一共放了n苹果,再把剩下的m-n个苹果放到n个盘子里
f(n,m)=f( n,m-n )
边界情况 第0列 第1行都要初始化为1
0 1 2 3 ..... m
1 1 1 1 1 1
2 1
3 1
..
n
*/
#include <iostream>
using namespace std;
int f[1010][1010] ;
int main()
{
int m,n;
while(cin>>m>>n)
{
//第1行 为1
for(int i=0;i<=m;i++)
f[1][i]=1;
//第0列 为1
for(int i=0;i<=n;i++)
f[i][0]=1;
for(int i=1;i<=n;i++ ) //i代表的是盘子数
{
for(int j=1;j<=m;j++) //j代表苹果数
{
if( j<i ) f[i][j]=f[j][j];
else
{
f[i][j]=f[i-1][j]+f[i][j-i];
}
}
}
cout<<f[n][m]<<endl;
}
return 0;
}
原始 暴力递归做法 tle
#include <iostream>
using namespace std;
int f(int m,int n)
{
if(n==1||m==0)
return 1;
if(m<n) return f(m,m);
else return f(m,n-1)+f(m-n,n);
}
int main()
{
int m,n;
while(cin>>m>>n)
{
cout<<f(m,n)<<endl;
}
return 0;
}
太强了太强了
大佬大佬我有个问题,我们在数组的初始化的时候,具体为数组哪一行哪一列初始化,又是初始化为0还是1,我们是自己带数据进去模拟一下来确定吗orz orz
根据实际具体情况,联想下,因为大规模n是从小规模n-1推出,所以就往小的边界去考虑,本题二维,小的边界就是
a) 1个苹果放在任意个盘子里,方案肯定只有一种
b) 任意个苹果放在0个盘子,1个盘子里,方案都是1种
太强了
膜拜dp大佬
orz
👍