dp聚类算法,dp动态规划算法

请注明出处。谢谢你。 http://blog.csdn.net/cc_again？ view mode=list ——-- ACC again 2014年5月15日

动态规划一直是ACM竞赛中的重点，同时又是难点，因为该算法时间效率高，代码量少，多元性强，主要考察思维能力、建模抽象能力、灵活度。

本人动态规划博客地址： http://blog.csdn.net/cc _ again/article/category/1261899

******************************************************************************************

http://www.Sina.com/(dynamic programming，DP )是数学、计算机科学和经济学中使用的一种通过将原始问题分解为相对简单的子问题来解决复杂问题的方法。动态规划常常应用于重叠问题和具有最优子结构性质的问题，动态规划方法往往比朴素解法耗时多。

动态规划背后的基本思想非常简单。一般来说，要解决某个问题，需要解决其不同的部分，即部分问题，合并部分问题的解得到原问题的解。通常，许多子问题非常相似。因此，动态规划法只尝试解决每个子问题一次，从而减少计算量。如果已经计算出了某个子问题的解，将其记忆并保存，下次需要同样的子问题的解时直接查表。如果重复子问题的数量随输入规模呈指数增长，则此方法尤其有用。

动态规划

动态规划问题满足三大重要性质如果问题的最优解中所包含的部分问题的解也是最优的，则该问题称为具有最优部分结构的性质(即满足优化原理)。最优子结构的性质为动态规划算法解决问题提供了重要线索。

最优子结构性质：部分问题重叠的性质是指，使用递归算法自顶向下地解决问题时，每次发生的部分问题并不总是新的问题，部分问题被反复计算多次。动态规划算法利用了这种子问题的重叠性质，每个子问题只计算一次，将其计算结果保存在一个表中，当需要再次计算计算完毕的子问题时，只需用表简单地看一下结果，就可以获得较高的效率。

子问题重叠性质：:按一定顺序排列各个阶段后，对于给定阶段的状态，之前的各个阶段的状态不能直接影响将来的决策，只能通过现在的这个状态。也就是说，各状态是过去历史的完整总结。这也被称为没有后向性，没有后效。

无后效性

********************************************************************************************

动态规划分类有很多划分方法，网上有很多是按照状态来分，分为一维、二维、区间、树形等等。我觉得还是按功能即解决的问题的类型以及难易程度来分比较好，下面按照我自己的理解和归纳，把动态规划的分类如下：

一、简单基础dp

这类dp主要是一些状态比较容易表示，转移方程比较好想，问题比较基本常见的。主要包括递推、背包、LIS（最长递增序列），LCS（最长公共子序列），下面针对这几种类型，推荐一下比较好的学习资料和题目。

1、递推：

简单：

hdu 2084数塔简单自上而下递归

hdu 2018母牛故事简单递推计数

hdu 2044蜜蜂…简单递归计数(Fibonacci ) ) ) ) ) ) ) ) ) )。

hdu 2041超级楼梯Fibonacci

hdu 2050折线分割平面搜索递推公式