Posted on 2006-08-07 00:56
oyjpart 阅读(1031)
评论(2) 编辑 收藏 引用
§硬币问题1：
有n种硬币，每种硬币的面值为vi元，且只有一枚，问用这n种硬币找零S元的方法数。
§设d[i][j]为前i种硬币组成j元的方法数。
d[i][j] = d[i-1][j] + d[i-1][j-vi]
d[0][0]=1,d[0][1…S]=0
§空间复杂度为O(n2),浪费！
d[0]=1; d[1…S]=0;
for (i=1; i<=n; i++)
{
for (j=S; j>=vi; j--)
{
d[j] += d[j-vi];
}
}
§硬币问题2：
有n种硬币，每种硬币的面值为vi元，有mi枚，问用这n种硬币找零S元的方法数。
d[0]=1;d[1…S]=0;
for (i=1; i<=n; i++)
{
for (j=S; j>=vi; j--) //对上一阶段
{
for(k=1;k<=mi;k++)
{
if (j-k*vi>=0) d[j] += d[j-k*vi];
}
}
}
§硬币问题3：
有n种硬币，每种硬币的面值为vi元，有无数枚，问用这n种硬币找零S元的方法数。
d[0]=1;d[1…S]=0;
for (i=1; i<=n; i++)
{
for (j=S; j>=vi; j--)
{
for(k=1;;k++)
{
if (j-k*vi>=0) d[j] += d[j-k*vi];
else break;
}
}
}
也可以这样写
d[0]=1; d[1…S]=0;
for (i=1; i<=n; i++)
{
for (j=vi;j<=S; j++)
{
d[j] += d[j-vi];
}
}
从中我们可以看出DP其实就是对重叠子问题的记忆化求解