{今天我们思考26}动态规划(DP)与排列组合

[pongba]

DP解题思路的阶段总结

像所有的新手一样，对一种算法思想的理解需要经历从肤浅（流于表面形式）到逐渐触摸到本质的过程。为什么说"逐渐"触摸到本质，是因为很多时候你并不确定一个解释是不是最本质的，有时候会有好几个等价的解释，各自在不同的时候具有启发。

比如对DP的理解，一开始我理解为"递推"，但实际上这是最肤浅的理解，对于如何在特定的问题中找到递推关系毫无帮助和启发。换言之，这只是一个描述性的总结，而不是一个建设性的总结，不含方法论。

做（看）了一些题目之后我开始总结关于"How"的方法，怎样寻找到递推关系（递推关系蕴含着子问题）。我得到一个简单的观察，如果一个问题里面含有n这个变量，考虑把n变成n-1的情况。

当然，这个方法是非常特殊的。实际上更具一般性的方法是不仅可以从n-1后面切一刀，还可以在任意地方切（譬如切成两个n/2规模的），以任意标准切（比如像快排那样的）。所有考虑各种切法中哪种能够最有利于建立子问题是有帮助的。

这个我姑且把它叫做通过直接切分问题来寻找子问题。

可是。这还是特殊了。因为显然这个方法不能解决所有的DP问题，连"多数"DP问题都未必能解决。譬如前面提到的很多人熟悉的"最大（小）和连续子序列"问题，就难以通过这种方法求解（可行，但思维难度较大。）。譬如上次Lee给的敲石头问题。那么，在知道了这几个问题的解法之后我继续思考这些解法里面是不是蕴含着更具一般性的解题方法。

看起来我找到了一个，就是分类讨论法，具体做法是：首先，写出可行解的一般形式，譬如a1, a2, ..., an。然后对其中的某个不确定的ai进行讨论。譬如旅行商问题里面对"下一个城市"进行讨论。当不确定时，讨论。讨论的每个分支都带来了进一步的确定性，从而将问题转化成一个子问题。

然后Lee提到，这个方法是自顶向下的，有时候不适于思考，譬如对敲石头问题。并提到一种自底向上，着重于构造"状态"的外推法。

那么，到目前为止，DP的一般性启发式思考方法就已经有了三种：

1. 通过直接对问题切分来探索子问题。
2. 通过对可行解的分类讨论来探索子问题。
3. 通过建立"状态"来自底向上地推导最终解。

可是，我心里还是不踏实，因为"离散"的知识是极其不利于记忆的，需要更多的练习才能在运用的时候"不由自主"的联想起，也容易忘掉。每次做DP题的时候，我都得把好几种指导性的思路一一费劲从脑袋里翻出来，然后尝试。实在很不爽。虽然也许DP题并没有万用的解题手法，但我还是希望能够尽量提取出不同手法之间的本质联系，如果能够将一组看上去离散的知识点统一在一个更具一般性，更本质的知识点下面，我们的知识树就多出了一个根节点，于是下次提取的时候只要提取出那个根节点，下面的几个子节点就会一一乖乖闪现。极大的降低记忆的复杂性。

那么，上面三种手法的本质联系到底是什么呢？有一次在路上走的时候我想出了一种解释。它也许不是最本质的，也许大牛们早就想到过，但是我觉得至少有两个好处：

1. 它能够cover以上三种手法，通过增加一个根节点，减少知识的记忆复杂性和易提取性。
2. 归纳抽象的过程本身就是一种锻炼，锻炼的是归纳抽象的能力。

这个解释就是：DP的可行解的形式大多是一个排列组合（典型的——旅行商问题）。大家都知道，穷举一个规模为N的排列组合复杂性是a^n的，也就是"组合复杂性"。而DP问题的所谓子问题，实际上就是对应最终解的那个排列组合的某个"子排列组合"（某种子集）。而正由于子排列组合的数目往往是多项式的，所以子问题往往重复出现，并且本质上只要计算并缓存所有子组合的最优情况。这就是为什么一个组合复杂性的穷举问题可以DP优化为多项式复杂度的问题。

这一解释也提供了如何探索子问题的一个通用方案：寻找可行解（一个排列组合）中的子组合。还是拿最大和连续子序列说事，其解的形式是：A[i], A[i+1], .., A[j-1], A[j]，其中i,j不确定。那么如何得到有意义的子组合呢？首先讨论A[j]，为什么要讨论，因为只要A[j]不确定，A[j-1]就不确定，就拿不出子组合来。对于一个确定的A[j0]，解的可能性为A[i], A[i+1], .., A[j0-1], A[j0]。其最优解依赖于子组合A[i], A[i+1], .., A[j0-1]，到这里子问题就不请子现了：A[i], A[i+1], .., A[j0-1], A[j0]和A[i], A[i+1], .., A[j0-1]的形式相同，意味着它们是同一个问题的不同阶表示。

当然，由于这个指导思想一般性大了点，所以实际问题中往往没有前面提到的三种手法寻找方案来得快——众所周知的是，越特定的手法解题面虽然越窄，但如果题目对口了解决起来也越快。但它至少有两个好处（前面说过了）。所以一般性和特殊性的手法都是有帮助的。

类似的，敲石头问题也可以通过这种手法来探索子问题。至少目前我做过的DP题似乎都可以借助这种手法来探索，当然，刚才说过了，未必是最快的，所以也许可以考虑用来做backup，当其它方案没有头绪的时候试试。

我的解题经验很有限，所以不知道这个手法的覆盖范围有多广。实际上一个更广的领域是"组合优化"。更上面提到的很像。但针对的问题就不仅止于DP了。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[silwile]

实际上，一个组合复杂性的穷举问题用DP只能优化为 伪 多项式复杂度的问题。因为这种问题的算法复杂度与输入的参数大小相关。

2008/6/4 pongba <pon...@gmail.com>:

DP解题思路的阶段总结

像所有的新手一样，对一种算法思想的理解需要经历从肤浅（流于表面形式）到逐渐触摸到本质的过程。为什么说"逐渐"触摸到本质，是因为很多时候你并不确定一个解释是不是最本质的，有时候会有好几个等价的解释，各自在不同的时候具有启发。

比如对DP的理解，一开始我理解为"递推"，但实际上这是最肤浅的理解，对于如何在特定的问题中找到递推关系毫无帮助和启发。换言之，这只是一个描述性的总结，而不是一个建设性的总结，不含方法论。

做（看）了一些题目之后我开始总结关于"How"的方法，怎样寻找到递推关系（递推关系蕴含着子问题）。我得到一个简单的观察，如果一个问题里面含有n这个变量，考虑把n变成n-1的情况。

当然，这个方法是非常特殊的。实际上更具一般性的方法是不仅可以从n-1后面切一刀，还可以在任意地方切（譬如切成两个n/2规模的），以任意标准切（比如像快排那样的）。所有考虑各种切法中哪种能够最有利于建立子问题是有帮助的。

这个我姑且把它叫做通过直接切分问题来寻找子问题。

可是。这还是特殊了。因为显然这个方法不能解决所有的DP问题，连"多数"DP问题都未必能解决。譬如前面提到的很多人熟悉的"最大（小）和连续子序列"问题，就难以通过这种方法求解（可行，但思维难度较大。）。譬如上次Lee给的敲石头问题。那么，在知道了这几个问题的解法之后我继续思考这些解法里面是不是蕴含着更具一般性的解题方法。

看起来我找到了一个，就是分类讨论法，具体做法是：首先，写出可行解的一般形式，譬如a1, a2, ..., an。然后对其中的某个不确定的ai进行讨论。譬如旅行商问题里面对"下一个城市"进行讨论。当不确定时，讨论。讨论的每个分支都带来了进一步的确定性，从而将问题转化成一个子问题。

然后Lee提到，这个方法是自顶向下的，有时候不适于思考，譬如对敲石头问题。并提到一种自底向上，着重于构造"状态"的外推法。

那么，到目前为止，DP的一般性启发式思考方法就已经有了三种：

1. 通过直接对问题切分来探索子问题。
2. 通过对可行解的分类讨论来探索子问题。
3. 通过建立"状态"来自底向上地推导最终解。

可是，我心里还是不踏实，因为"离散"的知识是极其不利于记忆的，需要更多的练习才能在运用的时候"不由自主"的联想起，也容易忘掉。每次做DP题的时候，我都得把好几种指导性的思路一一费劲从脑袋里翻出来，然后尝试。实在很不爽。虽然也许DP题并没有万用的解题手法，但我还是希望能够尽量提取出不同手法之间的本质联系，如果能够将一组看上去离散的知识点统一在一个更具一般性，更本质的知识点下面，我们的知识树就多出了一个根节点，于是下次提取的时候只要提取出那个根节点，下面的几个子节点就会一一乖乖闪现。极大的降低记忆的复杂性。

那么，上面三种手法的本质联系到底是什么呢？有一次在路上走的时候我想出了一种解释。它也许不是最本质的，也许大牛们早就想到过，但是我觉得至少有两个好处：

1. 它能够cover以上三种手法，通过增加一个根节点，减少知识的记忆复杂性和易提取性。
2. 归纳抽象的过程本身就是一种锻炼，锻炼的是归纳抽象的能力。

这个解释就是：DP的可行解的形式大多是一个排列组合（典型的----旅行商问题）。大家都知道，穷举一个规模为N的排列组合复杂性是a^n的，也就是"组合复杂性"。而DP问题的所谓子问题，实际上就是对应最终解的那个排列组合的某个"子排列组合"（某种子集）。而正由于子排列组合的数目往往是多项式的，所以子问题往往重复出现，并且本质上只要计算并缓存所有子组合的最优情况。这就是为什么一个组合复杂性的穷举问题可以DP优化为多项式复杂度的问题。

这一解释也提供了如何探索子问题的一个通用方案：寻找可行解（一个排列组合）中的子组合。还是拿最大和连续子序列说事，其解的形式是：A[i], A[i+1], .., A[j-1], A[j]，其中i,j不确定。那么如何得到有意义的子组合呢？首先讨论A[j]，为什么要讨论，因为只要A[j]不确定，A[j-1]就不确定，就拿不出子组合来。对于一个确定的A[j0]，解的可能性为A[i], A[i+1], .., A[j0-1], A[j0]。其最优解依赖于子组合A[i], A[i+1], .., A[j0-1]，到这里子问题就不请子现了：A[i], A[i+1], .., A[j0-1], A[j0]和A[i], A[i+1], .., A[j0-1]的形式相同，意味着它们是同一个问题的不同阶表示。

当然，由于这个指导思想一般性大了点，所以实际问题中往往没有前面提到的三种手法寻找方案来得快----众所周知的是，越特定的手法解题面虽然越窄，但如果题目对口了解决起来也越快。但它至少有两个好处（前面说过了）。所以一般性和特殊性的手法都是有帮助的。

[pongba]

2008/6/4 silwile <sil...@gmail.com>:

实际上，一个组合复杂性的穷举问题用DP只能优化为 伪 多项式复杂度的问题。因为这种问题的算法复杂度与输入的参数大小相关。

举一个例子？

[Eric]

如skyline 问题 和楼的高度是有关的

On 6月4日, 上午8时15分, pongba <pon...@gmail.com> wrote:
> 2008/6/4 silwile <silw...@gmail.com>:

[silwile]

背包问题

2008/6/4 pongba <pon...@gmail.com>:

[pongba]

具体一点啊。你说的是哪个版本的背包问题？复杂度又是如何不是多项式的？

2008/6/4 silwile <sil...@gmail.com>:

[Yong Yuan]

就是普通的背包问题：给定N种物品，每种物品的价值为p_i, 重量为w_i。背包最大容量为C。问如何装包可以获得最大价值。如果每种物品最多放一次，就是0/1背包问题。如果每种最多放n_i次，就是有界被包问题。如果每种随便放多少次，就是无界背包问题，也等价于子集求和问题。可惜不管哪种背包问题，解都是NP-hard。比如用DP来解，复杂度是O(nC)，貌似多项式算法，但是注意到该问题的输入的长度同C的位数成正比，而不是同C的值成正比。于是O(nC)就变成NP-Hard乐。这在黑话里叫伪多项式算法，因为这里的多项式同输入的值成多项式关系，而不是同多项式的长度。比如说当C为1000时，它的长度不过10 （1111101000）。狰狞的指数关系2^n就跳出来乐。

2008/6/4 pongba <pon...@gmail.com>:

[silwile]

前面g9老大已经讲了:-)
背包问题的复杂度是O(nW). W is the weight limit. not polynomial in input size.
这跟Factor问题是一样的。

2008/6/5 pongba <pon...@gmail.com>:

[pongba]

2008/6/5 Yong Yuan <y...@cs.toronto.edu>:

就是普通的背包问题：给定N种物品，每种物品的价值为p_i, 重量为w_i。背包最大容量为C。问如何装包可以获得最大价值。如果每种物品最多放一次，就是0/1背包问题。如果每种最多放n_i次，就是有界被包问题。如果每种随便放多少次，就是无界背包问题，也等价于子集求和问题。可惜不管哪种背包问题，解都是NP-hard。比如用DP来解，复杂度是O(nC)，貌似多项式算法，但是注意到该问题的输入的长度同C的位数成正比，而不是同C的值成正比。于是O(nC)就变成NP-Hard乐。这在黑话里叫伪多项式算法，因为这里的多项式同输入的值成多项式关系，而不是同多项式的长度。比如说当C为1000时，它的长度不过10 （1111101000）。狰狞的指数关系2^n就跳出来乐。

哦，天哪天哪（此处省去老六体若干字..）:D

[pongba]

2008/6/5 Yong Yuan <y...@cs.toronto.edu>:

就是普通的背包问题：给定N种物品，每种物品的价值为p_i, 重量为w_i。背包最大容量为C。问如何装包可以获得最大价值。如果每种物品最多放一次，就是0/1背包问题。如果每种最多放n_i次，就是有界被包问题。如果每种随便放多少次，就是无界背包问题，也等价于子集求和问题。可惜不管哪种背包问题，解都是NP-hard。比如用DP来解，复杂度是O(nC)，貌似多项式算法，但是注意到该问题的输入的长度同C的位数成正比，而不是同C的值成正比。于是O(nC)就变成NP-Hard乐。这在黑话里叫伪多项式算法，因为这里的多项式同输入的值成多项式关系，而不是同多项式的长度。比如说当C为1000时，它的长度不过10 （1111101000）。狰狞的指数关系2^n就跳出来乐。

看了一下wiki，里面举了一个另例子：常用的测试n是否为素数的算法也是伪多项式复杂度。
我理解为什么可以认为是指数复杂度的，然而我奇怪的是，这两个例子（背包，素数测试），为什么需将问题规模定义为n的位数，而不是n的值本身呢？

BTW. 照这么说求fib序列第n项的复杂度也是伪多项式的？！

BTW. Introduction2Algo和Algorithms这两本里面居然没有介绍？

[pongba]

2008/6/5 pongba <pon...@gmail.com>:

2008/6/5 Yong Yuan <y...@cs.toronto.edu>:

就是普通的背包问题：给定N种物品，每种物品的价值为p_i, 重量为w_i。背包最大容量为C。问如何装包可以获得最大价值。如果每种物品最多放一次，就是0/1背包问题。如果每种最多放n_i次，就是有界被包问题。如果每种随便放多少次，就是无界背包问题，也等价于子集求和问题。可惜不管哪种背包问题，解都是NP-hard。比如用DP来解，复杂度是O(nC)，貌似多项式算法，但是注意到该问题的输入的长度同C的位数成正比，而不是同C的值成正比。于是O(nC)就变成NP-Hard乐。这在黑话里叫伪多项式算法，因为这里的多项式同输入的值成多项式关系，而不是同多项式的长度。比如说当C为1000时，它的长度不过10 （1111101000）。狰狞的指数关系2^n就跳出来乐。

看了一下wiki，里面举了一个另例子：常用的测试n是否为素数的算法也是伪多项式复杂度。
我理解为什么可以认为是指数复杂度的，然而我奇怪的是，这两个例子（背包，素数测试），为什么需将问题规模定义为n的位数，而不是n的值本身呢？

wiki上看到这么一段：
The distinction between the value of a number and its length is one of encoding: if numeric inputs are always encoded in unary, then pseudo-polynomial would coincide with polynomial.

[silwile]

对，常用的测试n是否为素数的算法也伪多项式的复杂度。但是对于测试n是否为素数是属于P的，它存在一个8次方的多项式算法。素数测试将问题规模定义为n的位数还是很好理解的吧，因为在计算机中输入n的表示就是二进制的形式。

关于这个伪多项式问题， Kleinberg的Algorithm Design 这本书上有。

2008/6/5 pongba <pon...@gmail.com>:

[pongba]

2008/6/5 silwile <sil...@gmail.com>:

对，常用的测试n是否为素数的算法也伪多项式的复杂度。但是对于测试n是否为素数是属于P的，它存在一个8次方的多项式算法。素数测试将问题规模定义为n的位数还是很好理解的吧，因为在计算机中输入n的表示就是二进制的形式。

那就是说到底是不是伪多项式实际上是个伪问题咯？如wiki上说的，如果用1进制来表达n的话，伪多项式和多项式复杂度就统一起来了。

[Yong Yuan]

我也喜欢Algorithm Design这本书。个人觉得非常适合初学者和程序员。书一开始就给出稳定婚姻问题。从解决问题的角度入手，层层递进地讲解怎么设计，引出算法设计的一般方法。然后用几道常见题目引入常用算法的设计思路。奠定总纲后，后面的书就从不同的角度深化算法设计的方法。例题也有趣。个人相当喜欢从设计到分析的讲解思路。这种方法给读者（至少是程序员）诱人的动机。毕竟很多人读算法书是为了写出更强大的程序。尤其像我这种老人家，NADD症状严重，尤其需要令人信服的动机，不然就老走神。而且作者强调设计，反而提供了钻研算法分析的充分理由，很好地解释了要设计出正确高效的算法，形式化的分析是必要手段。为什要扩展？为什么要到处一堆引理？为什么要追究复杂度？为什么要泛化？为什么要特化？这些看来学究的行为自然地有了现实基础。加上这本书写得晓畅通透，就算你只看书不动手，也可以获得"好舒服，原来我也可以设计出这些算法啊。一点都不难嘛"这种类似K粉后的波浪状快感和幻觉。:-D

2008/6/5 silwile <sil...@gmail.com>:

[windstorm]

我帮我弟问一下，大学生初学者，刚学完C和数据结构，先看Algorithm Design好一些还是先看算法导论好一些？

我都没看过，所以没法建议

2008/6/5 Yong Yuan <y...@cs.toronto.edu>:

--
Yours Sincerely
Kun

blog: www.forwind.cn

[pongba]

2008/6/5 Yong Yuan <y...@cs.toronto.edu>:

我也喜欢Algorithm Design这本书。个人觉得非常适合初学者和程序员。书一开始就给出稳定婚姻问题。从解决问题的角度入手，层层递进地讲解怎么设计，引出算法设计的一般方法。然后用几道常见题目引入常用算法的设计思路。奠定总纲后，后面的书就从不同的角度深化算法设计的方法。例题也有趣。个人相当喜欢从设计到分析的讲解思路。这种方法给读者（至少是程序员）诱人的动机。毕竟很多人读算法书是为了写出更强大的程序。尤其像我这种老人家，NADD症状严重，尤其需要令人信服的动机，不然就老走神。而且作者强调设计，反而提供了钻研算法分析的充分理由，很好地解释了要设计出正确高效的算法，形式化的分析是必要手段。为什要扩展？为什么要到处一堆引理？为什么要追究复杂度？为什么要泛化？为什么要特化？这些看来学究的行为自然地有了现实基础。加上这本书写得晓畅通透，就算你只看书不动手，也可以获得"好舒服，原来我也可以设计出这些算法啊。一点都不难嘛"这种类似K粉后的波浪状快感和幻觉。:-D

啊哈，可以算是一篇书评了:)
这么好的书居然没有电子版，实在郁闷。使得我一直没有机会浏览。看来只能去借来看了..

[silwile]

赶紧去系图书馆借阿，我刚还了这本书。以前一直被我霸占着:D

2008/6/5 pongba <pon...@gmail.com>:

[Eric]

我这几天人在芝加哥 没空上机写 写了一半 写贴上来

====


pangba 我想是不是你有点过于追求"统一理论"了。就像物理上统一场理论一样，可能现实的动规题过于复杂了，总结一个大统一的理论反而是很难。

我们知道，动规实际上是一种思想，而不是一个具体的算法。因此把握什么时候能用这个思想才是最重要的，这个也是你想要找的。 我觉得你总结的那几条经
验， 就是找子问题的线索。 比如怎么切分来找子问题，怎么找转移方程。 我隐隐的感觉，这个总结出来的线索，脱离了动规的本质，反而阻碍了思考。

我们回到动规的本质上吧。动规这类方法，其实就是两个性质，一个是优化函数上的，全局最优蕴含局部最优性。 比如最长不下降子序列这个问题，全局的一个
解，在局部也是一个最长不下降子序列。 这是优化函数的性质。没有这个性质，拆子问题就是扯淡。 比如优化函数是：在一个长度为N的整数数组里面挑出最
多的元素，使他们的和模3 余2。 这样的题目也有N, 但是我还没想到动规怎么做，而且我倾向于动规做不了。 对于没有最优结构的函数，有时候还要转
成有最优结构的。 比如一 double 数组，有正有负，求一连续子序列，使得乘积最大。 请注意这时候函数 f 不存在全局蕴含局部。因为全局可能
是 9* (-2 )* (-3), 而局部是 -18, 是乘积最小而不是乘积最大。这时候，我们可以对函数做恰当的变换，即找 |f| 而不是
f, 最后再根据 f 的符号 找出最大的。 这样的做法，就可以把本来不是全局蕴含局部的变成全局蕴含局部的。这个优化函数的性质是动规必然需要的。
这样，在函数优化上才能拆成子问题上的函数优化，而不管子问题外的函数怎么取值。如果大家再深入研究就会发现，（我猜想）优化函数一定要是一个线性可分
函数 [f(x1,x2) = t1 f(x1) + t2 f(x2). ]。（或者能够通过一个连续单调函数映射到线性可分函数，比如矩阵乘法
题，等价于取对数后加法） 像我刚才说的mod3 , 以及非线性规划当中，是没有动态规划的影子的。

第二个是子问题结构 容我想清楚了贴上来 (拆子问题的一些方法应当在此类中)

至于转移方程 怎么找状态 有了上面的分析 都不难.
(未完)

====

On Jun 4, 2:27 am, pongba <pon...@gmail.com> wrote:
> DP解题思路的阶段总结
>

> 像所有的新手一样，对一种算法思想的理解需要经历从肤浅（流于表面形式）到逐渐触摸到本质的过程。为什么说"逐渐"触摸到本质，是因为很多时候你并不确定一个解 释是不是最本质的，有时候会有好几个等价的解释，各自在不同的时候具有启发。

>
> 比如对DP的理解，一开始我理解为"递推"，但实际上这是最肤浅的理解，对于如何在特定的问题中找到递推关系毫无帮助和启发。换言之，这只是一个描述性的总结， 而不是一个建设性的总结，不含方法论。
>
> 做（看）了一些题目之后我开始总结关于"How"的方法，怎样寻找到递推关系（递推关系蕴含着子问题）。我得到一个简单的观察，如果一个问题里面含有n这个变量 ，考虑把n变成n-1的情况。
>

> 当然，这个方法是非常特殊的。实际上更具一般性的方法是不仅可以从n-1后面切一刀，还可以在任意地方切（譬如切成两个n/2规模的），以任意标准切（比如像快 排那样的）。所有考虑各种切法中哪种能够最有利于建立子问题是有帮助的。

>
> 这个我姑且把它叫做通过直接切分问题来寻找子问题。
>
> 可是。这还是特殊了。因为显然这个方法不能解决所有的DP问题，连"多数"DP问题都未必能解决。譬如前面提到的很多人熟悉的"最大（小）和连续子序列"问题， 就难以通过这种方法求解（可行，但思维难度较大。）。譬如上次Lee给的

> 敲石头问题 <http://groups.google.com/group/pongba/msg/5e0a258fc35ca21c>

> 。那么，在知道了这几个问题的解法之后我继续思考这些解法里面是不是蕴含着更具一般性的解题方法。
>
> 看起来我找到了一个，就是分类讨论法，具体做法是：首先，写出可行解的一般形式，譬如a1, a2, ...,
> an。然后对其中的某个不确定的ai进行讨论。譬如旅行商问题里面对"下一个城市"进行讨论。当不确定时，讨论。讨论的每个分支都带来了进一步的确定性，从而将 问题转化成一个子问题。
>

> 然后Lee提到，这个方法是自顶向下的，有时候不适于思考，譬如对敲石头问题。并提到一种自底向上，着重于构造"状态"的外推法<http://groups.google.com/group/pongba/msg/67c8452583115bb9>
> 。

>
> 那么，到目前为止，DP的一般性启发式思考方法就已经有了三种：
>
> 1. 通过直接对问题切分来探索子问题。
> 2. 通过对可行解的分类讨论来探索子问题。
> 3. 通过建立"状态"来自底向上地推导最终解。
>

> 可是，我心里还是不踏实，因为"离散"的知识是极其不利于记忆的，需要更多的练习才能在运用的时候"不由自主"的联想起，也容易忘掉。每次做DP题的时候，我都 得把好几种指导性的思路一一费劲从脑袋里翻出来，然后尝试。实在很不爽。虽然也许DP题并没有万用的解题手法，但我还是希望能够尽量提取出不同手法之间的本质联 系，如果能够将一组看上去离散的知识点统一在一个更具一般性，更本质的知识点下面，我们的知识树就多出了一个根节点，于是下次提取的时候只要提取出那个根节点， 下面的几个子节点就会一一乖乖闪现。极大的降低记忆的复杂性。

>
> 那么，上面三种手法的本质联系到底是什么呢？有一次在路上走的时候我想出了一种解释。它也许不是最本质的，也许大牛们早就想到过，但是我觉得至少有两个好处：
>
> 1. 它能够cover以上三种手法，通过增加一个根节点，减少知识的记忆复杂性和易提取性。
> 2. 归纳抽象的过程本身就是一种锻炼，锻炼的是归纳抽象的能力。
>

> 这个解释就是：DP的可行解的形式大多是一个排列组合（典型的----旅行商问题）。大家都知道，穷举一个规模为N的排列组合复杂性是a^n的，也就是"组合复杂性 "。而DP问题的所谓子问题，实际上就是对应最终解的那个排列组合的某个"子排列组合"（某种子集）。而正由于子排列组合的数目往往是多项式的，所以子问题往往 重复出现，并且本质上只要计算并缓存所有子组合的最优情况。这就是为什么一个组合复杂性的穷举问题可以DP优化为多项式复杂度的问题。

>
> 这一解释也提供了如何探索子问题的一个通用方案：寻找可行解（一个排列组合）中的子组合。还是拿最大和连续子序列说事，其解的形式是：A[i], A[i+1],
> .., A[j-1],

> A[j]，其中i,j不确定。那么如何得到有意义的子组合呢？首先讨论A[j]，为什么要讨论，因为只要A[j]不确定，A[j-1]就不确定，就拿不出子组合 来。对于一个确定的A[j0]，解的可能性为A[i],

> A[i+1], .., A[j0-1], A[j0]。其最优解依赖于子组合A[i], A[i+1], ..,
> A[j0-1]，到这里子问题就不请子现了：A[i], A[i+1], .., A[j0-1], A[j0]和A[i], A[i+1], ..,
> A[j0-1]的形式相同，意味着它们是同一个问题的不同阶表示。
>

> 当然，由于这个指导思想一般性大了点，所以实际问题中往往没有前面提到的三种手法寻找方案来得快----众所周知的是，越特定的手法解题面虽然越窄，但如果题目对口 了解决起来也越快。但它至少有两个好处（前面说过了）。所以一般性和特殊性的手法都是有帮助的。
>
> 类似的，敲石头问题也可以通过这种手法来探索子问题。至少目前我做过的DP题似乎都可以借助这种手法来探索，当然，刚才说过了，未必是最快的，所以也许可以考虑 用来做backup，当其它方案没有头绪的时候试试。
>
> 我的解题经验很有限，所以不知道这个手法的覆盖范围有多广。实际上一个更广的领域是"组合优化<http://en.wikipedia.org/wiki/Combinatorial_optimization>
> "。更上面提到的很像。但针对的问题就不仅止于DP了。

[pongba]

2008/6/6 Eric <xu.ma...@gmail.com>:

pangba 我想是不是你有点过于追求"统一理论"了。就像物理上统一场理论一样，可能现实的动规题过于复杂了，总结一个大统一的理论反而是很难。

哦，我想这是个误会，我在文中提到，我其实只是想总结一个"小统一"(^_^)。以达到这样的效果：
1. 有利于将三种启发式探索方法归纳在一个根节点下，利于记忆。
2. 因为总结的都是探索手法，所以大可以不严密。譬如虽然不是凡涉及到N的题目都可以动规，但从探索的角度，总该往上面试一试吧。试错本来也是重要的启发法嘛:)

最优子结构的确DP的必要条件。但由于对最优子结构的判断往往是"事后验证"式的，即，总是要先摸清问题结构，才能去验证是否有最优子结构吧。而一旦弄清了问题结构后，验证最优子结构就从来都不是那个难点了。

DP的难点既然在寻找子问题上，所以我帖子中就单单总结这个了。

第二个是子问题结构 容我想清楚了贴上来 (拆子问题的一些方法应当在此类中)

期待这个部分:D
目前我看过的DP解题思路总结里面都没有谁能够令我满意的总结出DP的启发式解题思路，大多都是朦朦胧胧地说。

[Eric]

现在说第二部分, 子问题的部分.

在 pongba 的文章里面, 提到了一个重要的问题, 就是动态规划和排列组合之间的关系, pongba 师兄认为这个比原来的三个可能更接近本
质一点. 我认为, 其实这个性质, 恰好证明了一点: 动态规划绝大多数只能解组合优化问题. 当然, 造成这个的原因很多了, 比如状态必须可枚
举才能有组合形式的转移方程. 否则的话, 转移方程就不是简单的 max s \in CurrentState f(s,
previous_state) 的形式了. 所以我说, pongba 总结的, 实际上反映了动态规划的实用范围, 即较多的用在组合优化里面.
(大家可以看所有的动态规划的用例, 都基本上是降低原来一个可穷举问题的复杂度) 对于不可穷举问题, 比如连续函数的线性规划, 动态规划是没起什
么作用的.

了解了这一点, 我想我们回过头来看 pangba 的概括, 就会比较明白, 他的概括框出了动态规划的使用范围. 也就是组合优化(变量是有限取值
的) (顺带给 TAOCP做广告: Knuth 爷爷也是最喜欢组合优化的人, 所以新出的第四卷, 讲的全是生成图, 树, 排列 组合 啥的,
很有意思. )

那么, 是不是所有的组合优化问题都能被动态规划动态一下呢, 依我个人的看法, 不是. 这就牵扯到子问题的结构了: 不满足无后效应的组合优化问题
不能被动态规划解. (或者说, 带约束的组合优化问题) 比如著名的八皇后问题, SAT 问题. 这些问题的约束, 往往能影响其后的所有变量的取
值. (因为约束的影响). 如果我们把要解决的组合优化问题写成一个整数规划问题, 我们就会发现, 能够被动态规划解的那些问题, 基本上没有非
平凡约束. (如 x_1 * x_2 == 0 这样的就是非平凡, 如 x_1 >=0 这样的算平凡约束. ) 这些没有约束的问题, 是满足无
后效应的一个前提. 所以假如各位遇到有约束的, 基本上放弃动规这个思路. 除非约束的结构足够好. {所谓的无后效应, 就是说, 当前状态取值的
约束只和前一个状态有关, 如果八皇后分成 n 个皇后到 n-1 个皇后的子问题, 就发现 n-1 后皇后的状态对 第 n 个皇后都有影响, 那
么, 所谓的 n 到 n-1 就不简单了, 因为子问题不是 给一个 n 就完事了, 还得给出皇后的全部状态, 各位可以比较一下八皇后和8x8
棋盘上找出一个从左到右的路径, 使得和最大(假设每次可以往右上上, 或右, 或右下移动一格的那种棋子, 所走过的路径上数字和最大)} 这两个问
题的异同, 就知道为啥我说非平凡约束影响了无后效应了.

说完了约束, 就说到子问题结构了. 我们仍然用整数规划的眼光来看组合优化问题(我的研究方向就是最优化, 所以不自觉的用最优化的思想来看组合优
化) 就发现, 所谓的子问题结构, 就是固定某些变量之后, 问题任然是类似的形式. 看过 lambda 演算的同学都知道, 图灵机最喜欢的除
了循环, 顺序和分支, 其实还超级喜欢递归. 如快排, 分治那样的算法, 计算机可喜欢了.

=================

(继续未完)

下文准备说, 怎么分析子问题, 找出子结构. 和pangba 兄的思路有点不一样. 还是太忙, 找不到机器上网, 思路很快, 打字很慢,
sigh~~~



On Jun 6, 10:46 am, pongba <pon...@gmail.com> wrote:
> 2008/6/6 Eric <xu.math...@gmail.com>:

>
> > pangba 我想是不是你有点过于追求"统一理论"了。就像物理上统一场理论一样，可能现实的动规题过于复杂了，总结一个大统一的理论反而是很难。
>
> 哦，我想这是个误会，我在文中提到，我其实只是想总结一个"小统一"(^_^)。以达到这样的效果：
> 1. 有利于将三种启发式探索方法归纳在一个根节点下，利于记忆。

> 2. 因为总结的都是*探索*

> 手法，所以大可以不严密。譬如虽然不是凡涉及到N的题目都可以动规，但从探索的角度，总该往上面试一试吧。试错本来也是重要的启发法嘛:)
>

> 最优子结构的确DP的必要条件。但由于对最优子结构的判断往往是"事后验证"式的，即，总是要先摸清问题结构，才能去验证是否有最优子结构吧。而一旦弄清了问题 结构后，验证最优子结构就从来都不是那个难点了。

[Eric]

回答pangba 两个问题:

一般说 O(n) 请注意, 其实是 n 个输入. 比如排序, 其实是 N 个输入数字, 你怎么压缩, 输入规模至少要 n 位吧

至于判断素数啊, 背包大小啊, 这些输入的 N, 是一个数, 不是问题的输入规模. 问题的输入规模是n 表示成某进制以后的宽度.

算法复杂度上定义的N, 是输入的规模, 不是输入的数字噢. 如g9 所说, 狰狞的指数关系才保证大N不被分解, 要不RSA就很容易挂掉了噢 呵
呵. 一般人很容易混淆这两个N, 所以特此好为人师一下.

另外, 那个一进制统一的思想是不对的. log 不能以1为底, 2进制3进制这些算法阶意义上是等价的, 但是在1进制上不等价. 而且
unary 得写成 5 = 00000, 而不是 5=11111 :) 我们理解输入的规模为输入的描述复杂度. 这样, 可能容易理解一点.

On Jun 5, 3:53 am, pongba <pon...@gmail.com> wrote:
> 2008/6/5 pongba <pon...@gmail.com>:
>
>
>
> > 2008/6/5 Yong Yuan <y...@cs.toronto.edu>:
>
> >> 就是普通的背包问题：给定N种物品，每种物品的价值为p_i,

> >> 重量为w_i。背包最大容量为C。问如何装包可以获得最大价值。如果每种物品最多放一次，就是0/1背包问题。如果每种最多放n_i次，就是有界被包问题。如果 每种随便放多少次，就是无界背包问题，也等价于子集求和问题。可惜不管哪种背包问题，解都是NP-hard。比如用DP来解，复杂度是O(nC)，貌似多项式算 法，但是注意到该问题的输入的长度同C的位数成正比，而不是同C的值成正比。于是O(nC)就变成NP-Hard乐。这在黑话里叫伪多项式算法，因为这里的多项 式同输入的
> >> *值*成多项式关系，而不是同多项式的长度。比如说当C为1000时，它的长度不过10 （1111101000）。狰狞的指数关系2^n就跳出来乐。
>
> > 看了一下wiki，里面举了一个另例子：常用的测试n是否为素数的算法也是伪多项式复杂度。
> > 我理解为什么*可以认为*是指数复杂度的，然而我奇怪的是，这两个例子（背包，素数测试），*为什么需*将问题规模*定义为*n的位数，而不是n的值本身呢？

>
> wiki上看到这么一段：
> The distinction between the value of a number and its length is one of
> encoding: if numeric inputs are always encoded in

> unary<http://en.wikipedia.org/wiki/Unary_numeral_system>,
> then *pseudo-polynomial* would coincide with *polynomial*.

[pongba]

赞，先顶再慢慢看:-D

继续等待下集（下集----如何寻找子问题----是我最关心的方法论问题）

其实我自己的解题经验还很有限，其中还有超过一半是看，而不是做。不过我一直在努力争取从每道题目中总结出最多的方法性质的东西，尤其是较具一般性的方法。对于后者，组里的一堆算法牛人们比我有更大的发言权:-D

2008/6/7 Eric <xu.ma...@gmail.com>:

[李锋]

DP问题变化很多，实际上最好的抽象就是动态规划问题的定义。

There is an ordering on the subproblems, and a relation that shows how to solve a subproblem given the answers to "smaller" subproblems, that is, subproblems that appear earlier in the ordering.

事实上，这儿有两个关键字，一个是ordering,一个是subproblems。

最近刚好做了一些题目，大致有四个类别：
1.最长递增子序列问题。
2.最长公共子序列问题。
3.矩阵乘法链问题及。
4.背包问题。

问题1中实际上是简单的有向无环图问题，这类问题一般分析比较简单，只需要画出两两节点之间的连接关系以及代价，便可以顺利解决。当然，这类问题也有比较变态的变形，这个变形的问题我附在后边，供大家讨论。

问题2，3，4变形则比较多，但是大多数都能归到这几个类别中去，然后放在这个大环境中去思考，应该能起到很好的作用。关于2，3问题的简单衍生问题我放到了这儿。主要是三道题目的解答，思路分析的很简略，正如所述，动态规划问题，一旦找到了最优子结构，基本上问题就解决了，而如何找子结构这块儿，却是不好分析的。写的比较粗糙，还望见谅。
 

[附题目]

Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2n pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or
vertically adjacent squares (diagonal adjacency is fine).

 

(a) Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent columns) and describe these patterns.
Call two patterns compatible if they can be placed on adjacent columns to form a legal placement.

Let us consider subproblems consisting of the first k columns 1=<k<=n. Each subproblem can be assigned a type, which is the pattern occurring in the last column.

(b) Using the notions of compatibility and type, give an O(n)-time dynamic programming algorithm for computing an optimal placement.

在 08-6-6，pongba<pon...@gmail.com> 写道：

> beautiful are also regarded by other people as useful.

　　　　　　　　　　　　　　　　　　　　--- Donald Knuth
 

[pongba]

谢谢Eric:)

我能理解这个定义，我就是难以理解为什么一定要这样定义。也就是说，为什么对于数值N不也定义输入规模为N。

不过看了你的解释我又想了一下，忽然想通了，一个很简单的原则：

定义：令输入数据所总共占用的空间为S，问题的输入规模为I，则比如满足：

I/S = 常数

这样的话，如果输入的是一个数值N，那么N所占的空间就正比于它的二进制位数，而不是N本身。

不知道这个定义靠谱不？

然而，我有另一个疑问：快排里面的N个数，每个数又自身是一个数值数Ai，如果Ai非常非常大的话，对问题的复杂度毫无疑问也是有影响的，因为比较两个大整数Ai的复杂度正比于Ai的二进制位数而不是Ai本身，因此假设max(Ai位数)=m（也=logAi）的话，快排的复杂度应该是O(nm)。但由于在普通情况下用固定大小的类型（int，long）来存快排的数值，所以m为常数，才得到了O(n)的情况。

2008/6/7 Eric <xu.ma...@gmail.com>:

[Lee MaRS]

2008/6/8 pongba <pon...@gmail.com>:

谢谢Eric:)

我能理解这个定义，我就是难以理解为什么一定要这样定义。也就是说，为什么对于数值N不也定义输入规模为N。

不过看了你的解释我又想了一下，忽然想通了，一个很简单的原则：

定义：令输入数据所总共占用的空间为S，问题的输入规模为I，则比如满足：

I/S = 常数

这样的话，如果输入的是一个数值N，那么N所占的空间就正比于它的二进制位数，而不是N本身。 

不知道这个定义靠谱不？ 

然而，我有另一个疑问：快排里面的N个数，每个数又自身是一个数值数Ai，如果Ai非常非常大的话，对问题的复杂度毫无疑问也是有影响的，因为比较两个大整数Ai的复杂度正比于Ai的二进制位数而不是Ai本身，因此假设max(Ai位数)=m（也=logAi）的话，快排的复杂度应该是O(nm)。但由于在普通情况下用固定大小的类型（int，long）来存快排的数值，所以m为常数，才得到了O(n)的情况。

做算法分析的时候会有一些假设的，比如假设四则运算和比较的复杂度为O(1)。不同的假设下面得出的复杂度不一定一样的。一般来说，我们分析出来的复杂度是算法进行了多少步的渐进复杂度，而不是"计算"的复杂度。

以你的例子来说的话，如果不提出Ai本身非常非常大的条件，可以认为比较Ai就是O(1)的复杂度，但是如果提出这个条件的话，则比较Ai的复杂度不可忽略（O(1)就相当于忽略了）。这个时候，比较次数少的算法就占优势了。
 

[pongba]

2008/6/8 Lee MaRS <lee...@gmail.com>:

2008/6/8 pongba <pon...@gmail.com>:

谢谢Eric:)

我能理解这个定义，我就是难以理解为什么一定要这样定义。也就是说，为什么对于数值N不也定义输入规模为N。

不过看了你的解释我又想了一下，忽然想通了，一个很简单的原则：

定义：令输入数据所总共占用的空间为S，问题的输入规模为I，则比如满足：

I/S = 常数

这样的话，如果输入的是一个数值N，那么N所占的空间就正比于它的二进制位数，而不是N本身。 

不知道这个定义靠谱不？ 

然而，我有另一个疑问：快排里面的N个数，每个数又自身是一个数值数Ai，如果Ai非常非常大的话，对问题的复杂度毫无疑问也是有影响的，因为比较两个大整数Ai的复杂度正比于Ai的二进制位数而不是Ai本身，因此假设max(Ai位数)=m（也=logAi）的话，快排的复杂度应该是O(nm)。但由于在普通情况下用固定大小的类型（int，long）来存快排的数值，所以m为常数，才得到了O(n)的情况。

做算法分析的时候会有一些假设的，比如假设四则运算和比较的复杂度为O(1)。不同的假设下面得出的复杂度不一定一样的。一般来说，我们分析出来的复杂度是算法进行了多少步的渐进复杂度，而不是"计算"的复杂度。

以你的例子来说的话，如果不提出Ai本身非常非常大的条件，可以认为比较Ai就是O(1)的复杂度，但是如果提出这个条件的话，则比较Ai的复杂度不可忽略（O(1)就相当于忽略了）。这个时候，比较次数少的算法就占优势了。
 

OK，谢谢Lee，我也正是这样想的:0)
P.S. 那个"输入规模"定义靠谱不？

[Eric]

你说的对 你说的 S 就是朴素的描述复杂度的定义

其次, 请注意所有排序都假设比较是 O(1), 否则就不好谈复杂度了.

算法复杂度, 其实就是要假设一些原子操作的. 你看Knuth 爷爷的书, 才搞笑呢, 假设不同的操作还有不同的单位复杂度, 所以常常搞出复杂度
是:

9A+2B+6C+3D+E+13

(TAOCP, Vol 2, pp340)

现在的算法复杂度分析倾向于归并原子操作, 到了高爷爷那里, 全是把原子操作分开来的. 估计这样分析, pangba 你就相信 算法复杂度分析和
原子操作的定义有关了 :)

On Jun 8, 12:03 am, pongba <pon...@gmail.com> wrote:
> 谢谢Eric:)
>
> 我能理解这个定义，我就是难以理解为什么一定要这样定义。也就是说，为什么对于数值N不也定义输入规模为N。
>
> 不过看了你的解释我又想了一下，忽然想通了，一个很简单的原则：
>
> 定义：令输入数据所总共占用的空间为S，问题的输入规模为I，则比如满足：
>
> I/S = 常数
>
> 这样的话，如果输入的是一个数值N，那么N所占的空间就正比于它的二进制位数，而不是N本身。
>
> 不知道这个定义靠谱不？
>

> 然而，我有另一个疑问：快排里面的N个数，每个数又自身是一个数值数Ai，如果Ai非常非常大的话，对问题的复杂度毫无疑问也是有影响的，因为比较两个大整数A i的复杂度正比于Ai的二进制位数而不是Ai本身，因此假设max(Ai位数)=m（也=logAi）的话，快排的复杂度应该是O(nm)。但由于在普通情况下 用固定大小的类型（int，long）来存快排的数值，所以m为常数，才得到了O(n)的情况。
>
> 2008/6/7 Eric <xu.math...@gmail.com>:

[Jianshi Huang]

Here's my thoughts about DP:

1) State your problem in recursive style.
2) If you can draw a lattice (therefore it has order) from any start
condition of your problem to the base problem(s).
3) Then you can solve the problem using DP.

If you know memoizing, you know what I'm talking about.

On Jun 7, 8:54 pm, "李锋" <nemoking...@gmail.com> wrote:
> DP问题变化很多，实际上最好的抽象就是动态规划问题的定义。
>
> There is an ordering on the subproblems, and a relation that shows how to
>
> > solve a subproblem given the answers to "smaller" subproblems, that is,
> > subproblems that appear earlier in the ordering.
>
> 事实上，这儿有两个关键字，一个是ordering,一个是subproblems。
>
> 最近刚好做了一些题目，大致有四个类别：
> 1.最长递增子序列问题。
> 2.最长公共子序列问题。
> 3.矩阵乘法链问题及。
> 4.背包问题。
>
> 问题1中实际上是简单的有向无环图问题，这类问题一般分析比较简单，只需要画出两两节点之间的连接关系以及代价，便可以顺利解决。当然，这类问题也有比较变态的变形，这个变形的问题我附在后边，供大家讨论。
>

> 问题2，3，4变形则比较多，但是大多数都能归到这几个类别中去，然后放在这个大环境中去思考，应该能起到很好的作用。关于2，3问题的简单衍生问题我放到了这儿<http://okidogi.yo2.cn/articles/%25e7%25bb%258f%25e5%2585%25b8%25e5%25...>

> 。主要是三道题目的解答，思路分析的很简略，正如所述，动态规划问题，一旦找到了最优子结构，基本上问题就解决了，而如何找子结构这块儿，却是不好分析的。写的比较粗糙，还望见谅。
>
> [附题目]
> Pebbling a checkerboard. We are given a checkerboard which has 4 rows and n
> columns, and has an integer written in each square. We are also given a set
> of 2n pebbles, and we want to place some or all of these on the checkerboard
> (each pebble can be placed on exactly one square) so as to maximize the sum
> of the integers in the squares that are covered by pebbles. There is one
> constraint: for a placement of pebbles to be legal, no two of them can be on
> horizontally or
> vertically adjacent squares (diagonal adjacency is fine).
>
> (a) Determine the number of legal patterns that can occur in any column (in
> isolation, ignoring the pebbles in adjacent columns) and describe these
> patterns.
> Call two patterns compatible if they can be placed on adjacent columns to
> form a legal placement.
>
> Let us consider subproblems consisting of the first k columns 1=<k<=n. Each
> subproblem can be assigned a type, which is the pattern occurring in the
> last column.
>
> (b) Using the notions of compatibility and type, give an O(n)-time dynamic
> programming algorithm for computing an optimal placement.
>
> 在 08-6-6，pongba<pon...@gmail.com> 写道：
>

> > 2008/6/6 Eric <xu.math...@gmail.com>:

> > > pangba
> > 我想是不是你有点过于追求"统一理论"了。就像物理上统一场理论一样，可能现实的动规题过于复杂了，总结一个大统一的理论反而是很难。
>
> > 哦，我想这是个误会，我在文中提到，我其实只是想总结一个"小统一"(^_^)。以达到这样的效果：
> > 1. 有利于将三种启发式探索方法归纳在一个根节点下，利于记忆。
> > 2.
> > 因为总结的都是探索手法，所以大可以不严密。譬如虽然不是凡涉及到N的题目都可以动规，但从探索的角度，总该往上面试一试吧。试错本来也是重要的启发法嘛:)
>
> 最优子结构的确DP的必要条件。但由于对最优子结构的判断往往是"事后验证"式的，即，总是要先摸清问题结构，才能去验证是否有最优子结构吧。而一旦弄清了问题结构后，验证最优子结构就从来都不是那个难点了。
>
>
>
>
>
> > DP的难点既然在寻找子问题上，所以我帖子中就单单总结这个了。
>
> > > 第二个是子问题结构 容我想清楚了贴上来 (拆子问题的一些方法应当在此类中)
>
> > 期待这个部分:D
> > 目前我看过的DP解题思路总结里面都没有谁能够令我满意的总结出DP的启发式解题思路，大多都是朦朦胧胧地说。
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫
> >http://blog.csdn.net/pongba
> > TopLanguage
> >http://groups.google.com/group/pongba
>

> --
> The ideal situation occurs when the things that we regard as

[Jianshi Huang]

Therefore I think there're three essense in DP:

1) memory
2) order and convergence
3) recursion

[pongba]

2008/6/11 Jianshi Huang <jiansh...@gmail.com>:

Here's my thoughts about DP:

1) State your problem in recursive style.

Problem is "how". That's what we've been discussing about - methodology.

[Jianshi Huang]

How to solve the problem?

Recursion + Memoization

well, I heard some C++ compiler only suppor recursion with only 512
depth. Try some other languages like Scheme or Haskell.


On Jun 11, 6:54 pm, pongba <pon...@gmail.com> wrote:
> 2008/6/11 Jianshi Huang <jianshi.hu...@gmail.com>:

[pongba]

2008/6/11 Jianshi Huang <jiansh...@gmail.com>:

How to solve the problem?

Recursion + Memoization

well, I heard some C++ compiler only suppor recursion with only 512
depth. Try some other languages like Scheme or Haskell.

Check the above discussions, plz

[Jianshi Huang]

:) lol, what do you really want?

btw, 李锋's answer is closest to mine.

How can you recognize a DP structure in a given problem?

1) State your problem in recursive style.

2) If you can draw a lattice (therefore it has order) from any start

condition of your problem to the base problem(s) (whose answers are
already known).

3) Then you can solve the problem using DP.

How can you solve the problem after recognizing a DP structure in it?

Recursion + Memoization.

What's the essense of a DP structure?

1) memory
2) order and convergence
3) recursion

Of course, a DP structure doesn't guarantee that it can be solved in
polynomial time. The lattice you created when constructing your
recursive algorithm tells you the complexity of the algorithm. This
implies that different ways of constructing the recursive algorithm
might lead you to a better algorithm.

Is that not clear enough? :) Sorry I cann't type Chinese at the
moment.

Implementing DP is easy but constructing the recursive algorithm might
be hard.

Cheers,

On Jun 11, 7:09 pm, pongba <pon...@gmail.com> wrote:
> 2008/6/11 Jianshi Huang <jianshi.hu...@gmail.com>:
>
>
>

[pongba]

2008/6/11 Jianshi Huang <jiansh...@gmail.com>:

:) lol, what do you really want?

btw, 李锋's answer is closest to mine.

How can you recognize a DP structure in a given problem?

1) State your problem in recursive style.

每个人都知道DP问题的求解主要分为两步：找递推（自顶向下），通过表格化方法缓存子问题解（自底向上），这根本没什么好讨论的。

我们讨论的是如何完成第一步，即如何寻找问题中的递推关系。"找递推"不是一句咒语，一念，然后就能够成功找到递推了。大量的DP题目递推关系都不是那么好找的。而我们讨论正是怎样才能有效地找到那个要找的递推关系。

[Jianshi Huang]

Well, Okay. Then it's a hard problem.

The only thing I can think of is *Invariants*.

I need to go now. I'll write to you later.

BTW you don't need a specialized table, you only need a hash table.

On Jun 11, 7:50 pm, pongba <pon...@gmail.com> wrote:
> 2008/6/11 Jianshi Huang <jianshi.hu...@gmail.com>:
>
>
>

[Jianshi Huang]

"BTW you don't need a specialized table, you only need a hash table. "

I mean you don't need to solve it bottom-up. Top-down with hash-table
is the natual way to implement it.

[Jianshi Huang]

这个帖子的标题改成"如何寻找问题的递归表达"更为贴切。

我想不出有什么方法可以帮你找到递归，前面说的不变量也只是帮你验证你的算法的正确性。似乎递归的描述都是最直观的，往往根据问题的描述就可以获得。

能否举些难点的例子？

[pongba]

2008/6/11 Jianshi Huang <jiansh...@gmail.com>:

这个帖子的标题改成"如何寻找问题的递归表达"更为贴切。

我想不出有什么方法可以帮你找到递归，前面说的不变量也只是帮你验证你的算法的正确性。似乎递归的描述都是最直观的，往往根据问题的描述就可以获得。

能否举些难点的例子？

我做的题不多，但这里有很多算法牛人，召唤一下:-)

[Jianshi Huang]

OK, :)

Kal Vas Xen Corp~~~~

On Jun 11, 11:09 pm, pongba <pon...@gmail.com> wrote:
> 2008/6/11 Jianshi Huang <jianshi.hu...@gmail.com>:
>

[Guo]

是印度一个教授和他的两个学生提出来的，但实际应用中还是没有什么价值的

On 6月5日, 下午6时49分, pongba <pon...@gmail.com> wrote:
> 2008/6/5 silwile <silw...@gmail.com>:
>
>
>
> > 对，常用的测试n是否为素数的算法也伪多项式的复杂度。但是对于测试n是否为素数是属于P的，它存在一个8次方的多项式算法。素数测试将问题规模定义为n的位数-还是很好理解的吧，因为在计算机中输入n的表示就是二进制的形式。
>
> 那就是说到底是不是伪多项式实际上是个伪问题咯？如wiki上说的，如果用1进制来表达n的话，伪多项式和多项式复杂度就统一起来了。