oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

§硬幣問題1：
有n種硬幣，每種硬幣的面值為vi元，且只有一枚，問用這n種硬幣找零S元的方法數(shù)。
§設(shè)d[i][j]為前i種硬幣組成j元的方法數(shù)。
d[i][j] = d[i-1][j] + d[i-1][j-vi]
d[0][0]=1,d[0][1…S]=0
§空間復(fù)雜度為O(n2),浪費(fèi)！?
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元的方法數(shù)。
?
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元，有無數(shù)枚，問用這n種硬幣找零S元的方法數(shù)。
?
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其實(shí)就是對重疊子問題的記憶化求解