P170 动态规划

[SamZhangQingChuan]

以我一个算法竞赛选手的角度来看。。。这东西真的叫做搜索啊。。。

[winterland1989]

可否提供相关资料？以我的理解，动态规划是个比较宽泛的概念，基本上类似这篇博文的看法。其他一些资料也有把八皇后问题归类为动态规划的说法，所以可否认为这里的搜索是一种动态规划呢？

[SamZhangQingChuan]

下称动态规划为dp

1. 动态规划一般是用来解决最优化问题，八皇后这东西显然不是个最优化问题

2. 动态规划的两个要素是状态（或称子问题）和转移函数（也就是状态之间如何转移）

3. 我之所以把它称作搜索而不是动态规划是因为，你这个东西实际上就是遍历了一下解空间（当然加了点剪枝），本质上和暴力没啥区别。而动态规划被人使用的很重要的一点是他把相同的解合并了起来，从而达到了复杂度上的优越性（这里可能比较抽象，需要刷点题才能理解）

4. As far as I know, dp里面似乎没啥东西叫做heuristic啊，求教一下是哪里看到的概念

FYI：事实上一个dp算法对应了一个DAG（有向无环图（当然不是dag也可以跑dp只不过是用最短路）），其中node对应状态，edge对应转移函数

[winterland1989]

我如果没有理解错你的意思，你比较倾向于把子问题里使用了memorize技巧的一类算法划分为dp？

[SamZhangQingChuan]

这完全不是我的意思…… 我的意思是说，如果这个也能算动态规划的话，那么所有遍历解空间的算法你都可以称作使用了动态规划

[winterland1989]

我想很多人的看法可能和楼主并不相同，请参考这篇讨论。当然这里并不想引入关于动态规划的本质的争论，只是简单的阐述一下我在树下提到动态规划并不是完全没有根据的。

[ctzsm]

@winterland1989 请问在八皇后问题中，你如何定义状态和状态转移方程？

[winterland1989]

使用[]单子的例子里，状态就是存放在列表里的前m行的摆放方案，状态转移通过[]单子的bind实现，在后面使用foldM的版本里就更加明显了，placeQueen就是我们的状态转移。

[findmyway]

DP 的概念比较宽泛， @SamZhangQingChuan 所指的应该是OJ中常见的关于DP的理解，最核心的部分是状态和转移函数，不过这里的转移函数可以是很general的一类。

碰巧最近在看Reinforcement Learning. 最基本的部分就是DP，如果有兴趣可以看看这本书的Chapter4。

[SamZhangQingChuan]

@findmyway 我觉得遍历解空间怎么说都不能算dp啊、、、