int n = GetMinCoinCount2(m);
printf("计算凑成%d元最少需要的硬币数量,调用GetMinCoinCount2函数%d次。\r\n", m, g_i);
printf("%d\r\n", n);
}
for (int m = 12; m <= 100; m++)
{
g_i = 0;
memset(g_nMinArray, 0, sizeof(g_nMinArray));
int n = GetMinCoinCount2(m);
printf("计算凑成%d元最少需要的硬币数量,调用GetMinCoinCount2函数%d次。\r\n", m, g_i);
printf("%d\r\n", n);
}
打印输出的部分结果：
[cpp]
计算凑成94元最少需要的硬币数量,调用GetMinCoinCount2函数626次。
19
计算凑成95元最少需要的硬币数量,调用GetMinCoinCount2函数633次。
19
计算凑成96元最少需要的硬币数量,调用GetMinCoinCount2函数640次。
20
计算凑成97元最少需要的硬币数量,调用GetMinCoinCount2函数647次。
20
计算凑成98元最少需要的硬币数量,调用GetMinCoinCount2函数654次。
20
计算凑成99元最少需要的硬币数量,调用GetMinCoinCount2函数661次。
20
计算凑成100元最少需要的硬币数量,调用GetMinCoinCount2函数668次。
20
计算凑成94元最少需要的硬币数量,调用GetMinCoinCount2函数626次。
19
计算凑成95元最少需要的硬币数量,调用GetMinCoinCount2函数633次。
19
计算凑成96元最少需要的硬币数量,调用GetMinCoinCount2函数640次。
20
计算凑成97元最少需要的硬币数量,调用GetMinCoinCount2函数647次。
20
计算凑成98元最少需要的硬币数量,调用GetMinCoinCount2函数654次。
20
计算凑成99元最少需要的硬币数量,调用GetMinCoinCount2函数661次。
20
计算凑成100元最少需要的硬币数量,调用GetMinCoinCount2函数668次。
20
可以看出，通过保存中间状态的方式，我们将指数级的计算时间缩短到了线性级。
另外，我们上面的思路一直是递归的思路，通过将递归改成递推，我们可以减少不必要的函数调用和栈空间开销，进一步提高计算速度。相应代码如下：
[cpp]
int GetMinCoin(int nSum)
{
for (int i = 1; i <= nSum; i++)
{
if (1 == i || 4 == i || 5 == i)
{
g_nMinArray[i] = 1;
}
else if (i > 5)
{
g_nMinArray[i] = MIN_THREE(g_nMinArray[i-1], g_nMinArray[i-4], g_nMinArray[i-5])+1;
}
else if (i > 4)
{
g_nMinArray[i] = MIN_TWO(g_nMinArray[i-1], g_nMinArray[i-4])+1;
}
else
{
g_nMinArray[i] = g_nMinArray[i-1]+1;
}
}
return g_nMinArray[nSum];
}
int GetMinCoin(int nSum)
{
for (int i = 1; i <= nSum; i++)
{
if (1 == i || 4 == i || 5 == i)
{
g_nMinArray[i] = 1;
}
else if (i > 5)
{
g_nMinArray[i] = MIN_THREE(g_nMinArray[i-1], g_nMinArray[i-4], g_nMinArray[i-5])+1;
}
else if (i > 4)
{
g_nMinArray[i] = MIN_TWO(g_nMinArray[i-1], g_nMinArray[i-4])+1;
}
else
{
g_nMinArray[i] = g_nMinArray[i-1]+1;
}
}
return g_nMinArray[nSum];
}可以用这段代码的运行结果和上面递归代码的计算结果进行比较验证。这个例子就先讲到这里了，其实和斐波那契数列的求法在思想上挺类似（维基百科中文版的动态规划词条下就是用斐波那契数列来做例子的）。
在这里有一个很重要的思想就是保存中间子过程供多次使用，用空间换时间加快算法计算时间，这是动态规划算法的精髓。
第二个例子 路径经过的最大值（最小值）：
原题：平面上有N*M个格子，每个格子中放着一定数量的苹果。从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子就把格子里的苹果收集起来， 这样一直走到右下角，问最多能收集到多少个苹果。
不妨用一个表格来表示：
{5, 8, 5, 7, 1, 8},
{1, 3, 2, 8, 7, 9},
{7, 8, 6, 6, 8, 7},
{9, 9, 8, 1, 6, 3},
{2, 4,10, 2, 6, 2},
{5, 5, 2, 1, 8, 8},
在这个6X6的表格里面填写了一些数表示所在格子中的苹果数量。根据题目的规则"每一步只能向下走或是向右走"，如果用i表示纵向，用j表示横向，那么能够到达a[i][j]处的只有两个位置a[i-1][j](上一格)和a[i][j-1]（左边一格），所以必然是取这两个位置中比较大的那一个点。依此回溯到a[0][0]，或者从a[0][0]递推到a[i][j]。
......... , ......... , a[i-1][j]
......... , a[[i][j-1], a[i][j] ,
基于这一点，我们可以从左上角开始将到达第一行和第一列中各点所能收集到的最大苹果数量填成一张表格。如下：
接下来填第2行，首先是第2行第2列的值，应该填写为 MAX（A[1][2], A[2][1]）+ A[2][2]对应的苹果数量。也就是说到达第2行第2列能获得的最大苹果数，要看第2行第1列所获得的苹果数（6）和第1行第2列所获得的苹果数（13），这两者哪个更大，谁大就取谁的值，显然第1行第2列所获得的苹果数（13）更大，所以用13加上第2行第2列的苹果数3 = 16，就是到达第2行第2列能获得的最大苹果数。同理，填所在格能获得的最大苹果数就是看它左面一格和上面一格哪个值更大，就取哪个值再加上自己格子里面的苹果数，就是到达此格能获得的最大苹果数。依此填完所有格子，最后得到下图：
所以：到达右下角能够获得的最大苹果数量是