一道笔试题：捞鱼问题(二)
return dp[bucketN][fishN];
}
int main()
{
cout<
memset(dp,0,sizeof(dp));
cout<
system("pause");
return 0;
}
其实，代码还可以更简练，仔细想想，就是初始化状态的方法；其实初始化合法状态完全可以这样想，问题始终都是分解成子问题的，根据递归的实现方法，只有分解到0个桶装0条鱼才是合法的，那么我们就初始化这一个状态为合法即可，然后从第一个桶开始向上计算，代码如下：
[cpp]
#include
using namespace std;
int dp[21][200];
int i, j, k;
void main()
{
int bucketN, fishN;
scanf("%d %d", &bucketN, &fishN);
dp[0][0] = 1; /* 初始化合法状态 */
for(int i = 1; i <= bucketN; ++i) /* 从第一个桶开始 */
{
for(int j = 0; j <= fishN; ++j)
{
for(int k = 0; k <= 10 && j-k >= 0; ++k)
{
dp[i][j] += dp[i-1][j-k];
}
}
}
printf("%d\n",dp[bucketN][fishN]);
}
想不通我的空间优化怎么不成功，类似背包问题的优化，555555555555555555。有大神可以帮忙解释一下啊？
[cpp]
#include
#include
using namespace std;
int dp[200] = {0};
int FuncDp(int bucketN,int fishN)
{
int i,j,k;
for(i=0; i<=10; ++i)
dp[i] = 1;
for(i=2; i<=bucketN; ++i){
for(j=fishN; j>=0; --j){//反着遍历，防止覆盖
for(k=0; k<=10&&j-k>=0; ++k){//可以取0-10
dp[j] += dp[j-k];
}
}
}
return dp[fishN];
}
int main()
{
-->
| 评论 |
|
|