ACM动态规划问题（算法竞赛入门经典）

Question

刘汝佳的算法白皮书上DP三角形求最大和那道题，书上有3中方法，第一种是递归计算，第二种递推计算，第三种是记忆化搜索，请问这三种方法都是DP思想的体现吗？
到底什么是DP，每个DP问题都有状态转移方程吗？d(i,j) = a(i,j) + max{ d(i+1,j), d(i+1,j+1) }

Answer 1

递归就不说了，明显是需要栈的逻辑结构维护的。简单说说对递推和DP的个人见解，只供参考。

DP=状态+状态转移方程
状态的关键特点是无后效性，简单地举例：奥运会某项目淘汰赛1/N决赛，成绩只跟以后的比赛有关，之前的成绩不带入（只考虑赛制）。如果你发现一个状态后面阶段决策需要用到前面阶段的状态信息，那么这就不是一个标准的DP。比如：
A - B1 - C1 - D
\-- EX ------/
如果将EX归为B段或C段，那么EX-D或者A-EX就跨越了跳跃了一个阶段，对于这个阶段来说他后面的阶段就用到了前面阶段的状态信息
当然这并不意味着不能采用DP算法，对于上面的例子，可以将EX本身拆为B2 - C2就可以满足DP条件了，对于连续状态的DP，类似的调整更多。

状态转移方程是状态到状态的决策
简单地说，就是贪心的那一部分，多条路你选择一条路的过程

很多时候，递推和DP难以区分，一般情况，状态转移决策明显是“选择”的时候，会当做DP，而如果计算比重较大，会当做递推；状态调整比较多时，可能认为是递推；连续状态可以归为DP。
例：M*N的的带权格子，从左上走到右下，每次只能向右或下移动一格，求权值加和最大（小）的路径条数。

还有一个相关词叫做“递推规划”，有兴趣的话可以自己看下相关资料

解释之后答案很明显：DP要有状态转移方程。甚至可以说DP的关键就是状态转移方程。
你的第一个问题，希望你把书名报一下，我貌似没有白皮的

Answer 2

DP(dynamic programming)，中文就叫动态规划。

应该每个DP问题都有状态转移方程。但方程是多样的，需要自己建模。

例如，在百度百科“动态规划”中，就有一个同样的DP三角形的例子，其中求最小和的状态转移方程就是：f(i, j)=a[i, j] + min{f(i-1, j)，f(i-1, j - 1)}。

Answer 3

到底什么是DP 当你发现一个大问题能够分解成若干个同类型小问题就DP