一步一步教你如何调试 递归程序，
这篇帖子主要是介绍 递归 与 动态规划 之间是如何转换的，什么是递归估计不用多说，那么什么是 动态规划呢？
我理解的动态规划就是：
能够避免 直接 递归实现 中出现的重复运算的技术就是动态规划。
这里有三个关键词："直接"、"递归实现"、"重复运算"
也许最简单的, 也是众所周知的动态规划题目是 Fibonacci数列,
如果你不知道，说明你的老师也不知道，而且我为你感到难过。
但是，遗憾的是，本文将 选取另一个也是众所周知的动态规划题目：
二项式系数 C(m, n)
它的递推公式如下：
C(m, n) = C(m-1, n-1) + C(m-1, n), C(m, 0) = 1, C(m, m) = 1;
你或许会很惊讶，这是什么？我根本不熟悉嘛！
好吧，我想杨辉三角你应该不陌生，是个c语言的书籍都会有这道题，
那么，你还记不记得杨辉三角 与 二项式系数有那么一点点的关系呢？
记不得，翻书吧！
首先，我(不是我们)给出 C(m, n）的 直接递归实现。
#include <stdio.h>
int C(int M, int N);
int main(void)
{
printf("%d\n", C(5, 2));
getchar();
return 0;
}
int C(int M, int N)
{
if (N == 0 || M == N)
{
return 1;
}
return C(M-1, N-1) + C(M-1, N);
}
输出：10
那么， 这个实现直接吗？
当然直接，公式就是这样定义的啊。不是吗？
然后， 可以肯定的是这个实现有 重复运算，
肯定有，要不然不会拿这道题作为例程解析。
怎么样知道这个实现有 重复运算呢？
很简单，把递归调用路径打印出来看一眼就行了，仅仅是一眼。
在此之前，得确信你会 复制/粘帖 控制台中的内容，如果你还不会，
那么，请你百度一下吧。
我给函数多加一个参数用来记录 递归调用深度 (这项技术已经被我多次使用，不知你的技术敏感度怎么样，有没有留意过)？
然后，重新实现一下代码。
#include <stdio.h>
int C(int M, int N, int depth);
int main(void)
{
printf("\nc(5, 2) = %d", C(5, 2, 0));
getchar();
return 0;
}
int C(int M, int N, int depth)
{
int i, ret;
for (i = 0; i < depth; i++)
{
printf(" ");
}
printf("C(%d, %d)\n", M, N);
if (N == 0 || M == N)
{
return 1;
}
return C(M-1, N-1, depth+1) + C(M-1, N, depth+1);
}
输出：
C(5, 2)
C(4, 1)
C(3, 0)
C(3, 1)
C(2, 0)
C(2, 1)
C(1, 0)
C(1, 1)
C(4, 2)
C(3, 1)
C(2, 0)
C(2, 1)
C(1, 0)
C(1, 1)
C(3, 2)
C(2, 1)
C(1, 0)
C(1, 1)
C(2, 2)
c(5, 2) = 10
很明显的可以看出，C(1, 1)被多次运算过，当然不只是C(1, 1)了， 还有C(2, 1)呢？还有，...?
然后，怎么样避免这个实现中的重复运算呢？
还记得先前有个帖子 "打家看看这个递归的 为什么结果要存起来 不能直接返回T 求N的阶乘的递归都不要存结果" 吗？
好吧，接下来咱采用相同的技术：把结果保存起来。
#include <stdio.h>
#define M 5
#define N 2
int C(int m, int n, int depth);
int knownC[M+1][N+1] = {0};
int main(void)
{
printf("\nc(%d, %d) = %d\n", M, N, C(M, N, 0));
getchar();
return 0;
}
int C(int m, int n, int depth)
{
int i, ret;
for (i = 0; i < depth; i++)
{
printf(" ");
}
printf("C(%d, %d)\n", m, n);
if (knownC[m][n] != 0)
{
return knownC[m][n];
}
if (n == 0 || m == n)
{
ret = 1;
}
else
{
ret = C(m-1, n-1, depth+1) + C(m-1, n, depth+1);
}
return knownC[m][n] = ret;
}
输出：
C(5, 2)
C(4, 1)
C(3, 0)
C(3, 1)
C(2, 0)
C(2, 1)
C(1, 0)
C(1, 1)
C(4, 2)
C(3, 1)
C(3, 2)
C(2, 1)
C(2, 2)
c(5, 2) = 10
这个就是 所谓的 "自顶向下动态规划" 。
现在， 我们回到先前 所说的 "杨辉三角"，
利用杨辉三角解 C(m, n) 。
#include <stdio.h>
#define M 5
#define N 2
int main(void)
{
int C[M+2][M+2] = {0, 1};
int i, j;
for (i = 1; i < M+2; i++)
{
for (j = 1; j <= i; j++)
{
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
printf("%d\n", C[M+1][N+1]);
return 0;
}
这个就是 所谓的 "自底向上动态规划" 。
最后，请问你看懂了吗？
看懂了，请再看下 "出一个简单的算法题， 测测论坛的整体水平" 这个帖子，
并用三种方法解答出来，解不出来说明你还没看懂，希望你花点时间把它看懂。
小记：
先前和某人讨论 递归，他说递归多简单呀，然后还给我举了个例子,
就是 阶乘, 自此我对其非常不屑。
好吧， 我说完了，谢谢！
[ 本帖最后由 BlueGuy 于 2011-5-7 17:19 编辑 ]
