[今天我们思考20]DPDP

[pongba]

DP（Dynamic Programming）是非常经典也非常受欢迎的算法问题:-)

本帖有两个目的：

• 汇总大家做过的经典DP问题。
• 汇总大家在做DP问题的过程中的一般性的思考原则。（比如上次邓鋆提到的）

下面给出一道经典的，和一道可能陌生的：

1. 经典DP：用面值为1、2、5、10、20的纸钞组合出100块钱，一共有多少种可能。

2. 另类最大递增子序列问题：一个数组（其中每个元素都互不相同），它的子序列是指从原数组中抠掉若干个元素留下来的序列（因此并不要求连续）。递增子序列是指那些元素递增的子序列。最大递增子序列是指这样的一些递增子序列：无论从原数组中返还哪个元素，都不会使得这个子序列再增长为一个更长的递增子序列了。（注意，最大递增子序列不同于最长递增子序列。）求一个算法，返回一个数组中的最大递增子序列的个数。

英文描述：
A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.

For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.

（问题转载自：http://hi.baidu.com/rangemq）

2'. 第2个问题的"原始"版本是"最长递增子序列"问题：最长递增子序列问题要求一个算法返回数组中最长的递增子序列的长度。问题严格描述如下：设L=<a₁,a₂,…,a_n>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<a_K1,a_k2,…,a_km>，其中k₁<k₂<…<k_m且a_K1<a_k2<…<a_km。求最大的m值。

希望大家提供更多好的DP问题（LCS这样的经典问题，还有算法导论上的几个教科书式问题就不说了）:-)

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

[怀宇范]

抛砖引玉。。。
最近在翻算法导论的动态规划，正琢磨这类题目该如何分析。。。
我觉着倒着干的方式比较自然，从结果出发，分析结果有几种可能组成，寻找到一个可递归的规律。好处是比较容易想，而且可以联系上分治，贪心等。。。

1. 100中的组成，可能包含0～5个20（最大面值），用a(总数, 可用的钞票数) All( a(100,4) + a(80, 4) + ...  +a(0,4))...BTW  怎么感觉成了分治。。。
2. 一时没看懂题目。。。
2'. 最长递增子数列，包含max(包含最后一个，不包含最后一个）

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

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo(" fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[Jun Wang]

生物信息学中序列联配用到过DP算法，例如smith-waterman algorithm 用于找出一个长字串中与某短串最为匹配的子串的算法。

http://en.wikipedia.org/wiki/Smith-Waterman_algorithm

2008/5/15 怀宇范 <dugu...@gmail.com>:

[Gohan]

http://www.concretevitamin.com.cn/informatics/Pack/Index.html
背包问题九讲，对于经典背包问题的进一步扩展探讨，由浅入深

On 5月14日, 下午7时22分, pongba <pon...@gmail.com> wrote:
> DP（Dynamic Programming）是非常经典也非常受欢迎的算法问题:-)
>

> 本帖有*两个目的*：
>
> - 汇总大家做过的经典DP问题。
> - 汇总大家在做DP问题的过程中的*一般性的*思考原则。（比如上次邓鋆提到的<http://groups.google.com/group/pongba/msg/c636438aa32a56da>
> ）

[pongba]

DD牛的背包九讲！不错不错，谢谢分享～

2008/5/15 Gohan <cppg...@gmail.com>:

[Kenny]

收藏一下，回头看

[silwile]

好像dd牛还是个高中生阿。
写着真好。

2008/5/15 Gohan <cppg...@gmail.com>:

[pongba]

浙大吧

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

[Lee MaRS]

DP题的话做多了就会有心得了呵呵。核心思想是设计出一种状态表示，这种状态表示足够描述问题，可以求出问题的解，并且满足最优子结构。

2.题应该算是递推而不是DP，因为不存在最优化的过程。

2'的话不知道O(nlogn)的解法是否已经白菜了？

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

[dd_engi]

大家好……仰慕很久的pongba大牛好。我是DD，其实是高三学生，不过被浙大提前录取，目前在浙大修学分，虽然九月才正式入学大一。
背包九讲是我去年的不成熟之作，没想到这么多人从中受益，近期将大幅修订，请大家鞭策我。我会写更多DP相关的由浅入深的文章。
发个去年举办的DP题目比赛供参考：http://infowire.googlegroups.com/web/DP07Final.zip

On May 16, 9:58 pm, pongba <pon...@gmail.com> wrote:
> 浙大吧
>
> 2008/5/16 silwile <silw...@gmail.com>:
>
>
>
> > 好像dd牛还是个高中生阿。
> > 写着真好。
>
> > 2008/5/15 Gohan <cppgo...@gmail.com>:

[lbaby]

佩服，呵呵

On May 19, 11:40 am, dd_engi <tianyi...@gmail.com> wrote:
> 大家好......仰慕很久的pongba大牛好。我是DD，其实是高三学生，不过被浙大提前录取，目前在浙大修学分，虽然九月才正式入学大一。

> > >> ,a2,...,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,...,akm>，其中k1<k2<...<km且aK1<ak2
> > >> > <...<akm。求最大的m值。

[Concrete Vitamin]

考虑最大加权矩形问题 (二维), 从退化版最大和子序列 (一维) 开始思考有什么很明显的推动作用么?

2008/5/19 lbaby <lba...@yahoo.com.cn>:

[dd_engi]

有啊。直接把朴素算法跟那个结合起来，O(N^4)降到O(N^3)。

On May 19, 12:44 pm, "Concrete Vitamin" <concretevita...@gmail.com>
wrote:

[Concrete Vitamin]

这个思路的顺序应该是
原问题 -> 得出一个明显的朴素算法 -> 考虑降维问题 -> 改善原算法吧...
如果是先考虑降维问题的话我觉得没啥用处...

2008/5/19 dd_engi <tian...@gmail.com>:

[dd_engi]

这个思路太想当然的死板了吧，没有思路的顺序“应该是”什么的说法吧。就以我对这个问题了解过程来说，我是先看到过一维的O(N)算法，掌握了以后，后
来遇到了二维的问题，联想到曾经做过的降维的问题，就想到了O(N^3)的算法。
还有就像我以前懂得一维RMQ，在考场上遇到了二维问题，再把它推广到二维，很多时候情况是这样的，并不存在一个一以贯之的明晰的过程。

On May 19, 12:51 pm, "Concrete Vitamin" <concretevita...@gmail.com>
wrote:

> 这个思路的顺序应该是
> 原问题 -> 得出一个明显的朴素算法 -> 考虑降维问题 -> 改善原算法吧...
> 如果是先考虑降维问题的话我觉得没啥用处...
>

> 2008/5/19 dd_engi <tianyi...@gmail.com>:

[pongba]

2008/5/19 dd_engi <tian...@gmail.com>:

大家好……仰慕很久的pongba大牛好。我是DD，其实是高三学生，不过被浙大提前录取，目前在浙大修学分，虽然九月才正式入学大一。
背包九讲是我去年的不成熟之作，没想到这么多人从中受益，近期将大幅修订，请大家鞭策我。我会写更多DP相关的由浅入深的文章。
发个去年举办的DP题目比赛供参考：http://infowire.googlegroups.com/web/DP07Final.zip

果然是高中啊，牛啊:-)
期待DD写出更好的算法介绍!

[xxmplus]

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

>
>
> 2008/5/19 dd_engi <tian...@gmail.com>:
>>
>> 大家好……仰慕很久的pongba大牛好。我是DD，其实是高三学生，不过被浙大提前录取，目前在浙大修学分，虽然九月才正式入学大一。
>> 背包九讲是我去年的不成熟之作，没想到这么多人从中受益，近期将大幅修订，请大家鞭策我。我会写更多DP相关的由浅入深的文章。
>> 发个去年举办的DP题目比赛供参考：http://infowire.googlegroups.com/web/DP07Final.zip
>
> 果然是高中啊，牛啊:-)
> 期待DD写出更好的算法介绍!

达者为先，pfpf

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

--
Any complex technology which doesn't come with documentation must be the best
available.

[pongba]

再转一个：中国国家集训队论文集(1999-2008)
http://oibh.org/bbs/thread-16840-1-1.html

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

[silwile]

欢迎欢迎。

2008/5/19 dd_engi <tian...@gmail.com>:

[pongba]

借花献佛，经典动态规划题集，见附件。

来源于DD牛所在的OIBH团队的论坛：
http://oibh.org/bbs/thread-18327-1-1.html

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

[Concrete Vitamin]

OIBH 其实原指那个论坛, DD 牛搞 ACM 起的队名是 OIBH, 那个论坛并不是他的团队的论坛.......

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

[pongba]

哦，原来因果关系弄颠倒了。感谢纠正！:)

2008/5/19 Concrete Vitamin <concret...@gmail.com>:

[Lee MaRS]

借帖确认一下，我发的信能收到么- -b

前面回过本帖一次，貌似被无视了。。

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

[pongba]

2008/5/18 Lee MaRS <lee...@gmail.com>:

DP题的话做多了就会有心得了呵呵。核心思想是设计出一种状态表示，这种状态表示足够描述问题，可以求出问题的解，并且满足最优子结构。

2.题应该算是递推而不是DP，因为不存在最优化的过程。

2'的话不知道O(nlogn)的解法是否已经白菜了？

收得到，不是无视，而是看贴不一定回帖的。
习惯看贴不回贴者是发帖者必备心理素质哈:-)

回复如下：

DP题做得多了就会有心得了。

所有题做多了都会有心得的。稍有总结能力的人总能通过大量的联系达到触类旁通的效果的，这是人脑天生的能力。况且做题本身还有一个关键的作用就是积累知识。

不过，关键的问题是，什么样的总结和练习更为高效。

核心思想是设计出一种状态表示，这种状态表示足够描述问题，可以求出问题的解，并且满足最优子结构。

当然。但真正难的部分不在这里，而在如何找到这样一种状态表示，或递推关系，或子问题分割。有了奋斗的目标并不够，还要有达到目标的方法论呀。关于DP问题求解的一般性方法，目前还在思考和总结，正在读DD的《背包九讲》和99年国家集训论文集中来煜坤同学的《动态规划深入探讨》，有谁有更多相关总结式论文的还望相告:)

BTW. 为什么连《Algorithms》这样的书里面都只讲例子不讲方法？令人失望。难道DP问题求解并没有一般性的启发式方法？那较为特殊一点的（cover 的问题类型窄一点的）也没有？就我有限的经验，还是有一些指导性的探索方法的，虽然我还没有细细总结，待看完上面两篇论文先。

[Lee MaRS]

也是。订了这个邮件列表很久了，不过一直没怎么看，等我发现这个专题的时候编号都20了汗。以后要争取多说点有用的东西，这样估计回帖的热情会比较高。

至于你后面的几个问题，我也回答不好。我几年观察下来的经验，解题，尤其是解难题，往往是靠灵光一闪。对于简单的题目，倒是有比较易寻的思路。

不过思路这种东西，对一个人来说适用，对另一人来说未必适合。

至于DP，不妨尝试从另一个角度来理解：消除冗余计算，对于同一个状态，计算且只计算一次。

DP不是一个算法，只是一种思路，呵呵。:-)

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

[dd_engi]

> 不过，关键的问题是，什么样的总结和练习更为高效。
>
> 核心思想是设计出一种状态表示，这种状态表示足够描述问题，可以求出问题的解，并且满足最优子结构。
>
>
>
> 当然。但真正难的部分不在这里，而在如何找到这样一种状态表示，或递推关系，或子问题分割。有了奋斗的目标并不够，还要有达到目标的方法论呀。关于DP问题求解的一般性方法，目前还在思考和总结，正在读DD的《背包九讲》和99年国家集训论文集中来煜坤同学的《动态规划深入探讨》，有谁有更多相关总结式论文的还望相告:)

没错，我也曾经一直在探求解决DP问题的思考方式，或者一般性方法，但是每次有了大致的轮廓又被新见到的更难的题目推翻。

刚刚的想法是，DP题，与平面几何题非常类似：
1. 最基本的知识（公理）相对较少，但由最基本的东西推导出来的体系无比庞大、丰富而美妙。
2. 你做了越多此类题，完美解决遇到的下一道题的可能性越大，速度越快。
3. 存在一些多次出现的patterns，例如几何中的“旋转变换构造辅助图形”或者“通过反演简化图形”，DP中的“根据时间划分阶段”或者“在状
态中增加一维以消除后效性”。
4. 很难，如果不说“不可能”的话，找到一种求解的通用思路，或者一般性方法。了解得再多，总还会遇到做不出的题。
5. 最后，都很有趣，成功解出这类题目的感觉都很美妙。

嗯……话说在中学数学竞赛里面平面几何是重头戏，而在中学的计算机竞赛里面对应的就是DP了。:-)

On May 19, 9:18 pm, pongba <pon...@gmail.com> wrote:
> 2008/5/18 Lee MaRS <leem...@gmail.com>:

[silwile]

赞。
果然是踏踏实实走过来的人说的话。

2008/5/20 dd_engi <tian...@gmail.com>: