零、先修课程
首先，在开始理解DP的思想前，你需要
1. 完成HDU里面的递推求解专题练习（For Beginner）那7道题（这些题很简单，题解请在博客中搜索），这对你理解DP有很大的帮助。
2. 对递归搜索（比如深度优先搜索，DFS）有一定了解。
一、递归与记忆化搜索
我们从POJ 3176入手来学习这一思想。（题目很短，请快速读完）
从上往下看，最大和值无非是往左走和往右走这两条路的较大者。这样，我们可以写出下面这个重要的递归函数：（这里i表示行，j表示列）
int f(int i, int j)
{
if (i == n - 1) return a[i][j];
return a[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
但是，当我们编完整个程序并通过了样例后，提交后却返回了一串鲜红的文字：
What happened?
我们仔细分析程序，发现当我们从(0,0)往下走时，路越走越多，和细胞分裂一样，最终的路大约有2^n条！
这实在是太吓人了，当我们回过神来，程序早已崩溃（爆栈）。
冷静点，孩子。让我们再仔细地看看所给的数据吧，嗯，一个三角形大小的数据，准确地说，是n(n+1)/2个数。
按常理来说，实际的路也只有约n^2条，怎么可能会产生指数级别的路径数呢？
没错，重复。
重复的计算造成了程序的最终崩溃，而减少重复的计算是程序优化的一个永恒的主题。
那么，重复在哪里，如何减少重复的计算？
再来看看题目所给的样例，我们把目光放在1这个点上：我们可以从7-3-1到达1，继续往下面算，也可以从7-8-1到达1，继续往下面算。因此，在上面的代码中，在1这个点我们算了两遍！同样的遭遇也发生在1下面的那些点中。大量的重复计算最终导致了指数条路径的产生。
所以，我们不妨在计算一个点之前，先看看它有没有已经被计算出来。
怎么看？嗯……也许我们需要一个辅助的数组来保存计算的结果，比如这样：
int f(int i, int j)
{
if (dp[i][j] >= 0) return dp[i][j];
if (i == n - 1) return dp[i][j] = a[i][j];
return dp[i][j] = a[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
由于a[i][j]可能为0，所以需要在main()中把dp初始化为-1：
memset(dp, -1, sizeof(dp));
最终，程序返回了我们想看到的结果：
此题的完整代码见这篇文章。
PS：关于打印路径的方法，见下面的第三部分。
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索重复
， 递归
， dp
， 动态规划
， 搜索
， 程序
， return
， 路径规划怎么改文字
一个
dp动态规划、动态规划入门、数位dp入门、dp801单片机系统入门、树形dp入门，以便于您获取更多的相关知识。