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

递归就不说了,明显是需要栈的逻辑结构维护的.简单说说对递推和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的关键就是状态转移方程.
你的第一个问题,希望你把书名报一下,我貌似没有白皮的