动态规划算法 (二)

for (int m = 12; m < 30; m++)
{
g_i = 0;
int n = GetMinCoinCount(m);
printf("计算凑成%d元最少需要的硬币数量,调用GetMinCoinCount函数0x%08X次。\r\n", m, g_i);
}

计算凑成12元最少需要的硬币数量,调用GetMinCoinCount函数0x00000A3C次。
计算凑成13元最少需要的硬币数量,调用GetMinCoinCount函数0x0000184B次。
计算凑成14元最少需要的硬币数量,调用GetMinCoinCount函数0x00003535次。
计算凑成15元最少需要的硬币数量,调用GetMinCoinCount函数0x00003F7A次。
计算凑成16元最少需要的硬币数量,调用GetMinCoinCount函数0x00011692次。
计算凑成17元最少需要的硬币数量,调用GetMinCoinCount函数0x0004951B次。
计算凑成18元最少需要的硬币数量,调用GetMinCoinCount函数0x000A1756次。
计算凑成19元最少需要的硬币数量,调用GetMinCoinCount函数0x001561CA次。
计算凑成20元最少需要的硬币数量,调用GetMinCoinCount函数0x00180DE3次。
计算凑成21元最少需要的硬币数量,调用GetMinCoinCount函数0x006A7855次。
计算凑成22元最少需要的硬币数量,调用GetMinCoinCount函数0x01C2A51C次。
计算凑成23元最少需要的硬币数量,调用GetMinCoinCount函数0x03E4E8B7次。
计算凑成24元最少需要的硬币数量,调用GetMinCoinCount函数0x083F6AC5次。
计算凑成25元最少需要的硬币数量,调用GetMinCoinCount函数0x09447736次。
计算凑成26元最少需要的硬币数量,调用GetMinCoinCount函数0x29019F66次。
计算凑成27元最少需要的硬币数量,调用GetMinCoinCount函数0xAD92F423次。

显然，这样的递归算法是不可取的。我们分析一下问题的原因，就是因为同一个数值在递归函数中进行了多次计算，比如我们仍然以凑够12元为例，下图可以形象地展示计算过程：

vc3VuMjA0MzQzMA==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" />

由此图我们可以看出，存在大量的重复计算。比如图中的7。整个树上的节点增长速度是指数级的，树的最大深度为12层。每个节点的孩子节点为0到3个不等。

如果我们能够消除重复计算，将大大提升计算的速度。我们可以将计算出来的中间值保存起来，等下一次需要时直接拿来用，而不是又重新去计算一遍。

那么中间状态有多少种情况呢？对于凑成12元来说，所有可能需要用到的中间状态也就是从1元到11元。所以我们用一个数组来表示，代码修改如下。

[cpp]
int g_nMinArray[100] = {};
int g_i = 0;
int GetMinCoinCount2(int nSum)
{
g_i++;
if (0 != g_nMinArray[nSum])
{
return g_nMinArray[nSum];
}
if (1 == nSum || 4 == nSum || 5 == nSum)
{
g_nMinArray[nSum] = 1;
return 1;
}
if (nSum > 5)
{
g_nMinArray[nSum] = MIN_THREE(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4), GetMinCoinCount2(nSum-5))+1;
}
else if (nSum > 4)
{
g_nMinArray[nSum] = MIN_TWO(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4))+1;
}
else
{
g_nMinArray[nSum] = GetMinCoinCount2(nSum-1)+1;
}
return g_nMinArray[nSum];
}

int g_nMinArray[100] = {};
int g_i = 0;
int GetMinCoinCount2(int nSum)
{
g_i++;
if (0 != g_nMinArray[nSum])
{
return g_nMinArray[nSum];
}
if (1 == nSum || 4 == nSum || 5 == nSum)
{
g_nMinArray[nSum] = 1;
return 1;
}
if (nSum > 5)
{
g_nMinArray[nSum] = MIN_THREE(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4), GetMinCoinCount2(nSum-5))+1;
}
else if (nSum > 4)
{
g_nMinArray[nSum] = MIN_TWO(GetMinCoinCount2(nSum-1), GetMinCoinCount2(nSum-4))+1;
}
else
{
g_nMinArray[nSum] = GetMinCoinCount2(nSum-1)+1;
}
return g_nMinArray[nSum];
}相应的测试代码如下：

[cpp]
for (int m = 12; m <= 100; m++)
{
g_i = 0;
memset(g_nMinArray, 0, sizeof(g_nMinArray))