Posted on 2006-08-07 00:56
oyjpart 閱讀(1038)
評論(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其實就是對重疊子問題的記憶化求解