动态规划（DP）入门

动态规划（DP）入门2014-07-27 csdn博客 synapse7零、先修课程

首先，在开始理解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：关于打印路径的方法，见下面的第三部分。