什么是dp算法?

发布网友发布时间：2022-04-29 21:51

共4个回答

热心网友时间：2022-06-23 17:12

DP算法是解决多阶段决策过程最优化问题的一种常用方法。
多阶段决策过程（multistep decision process）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。动态规划（dynamic programming）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。
动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。

热心网友时间：2022-06-23 17:12

DP指动态规划.可以理解为通过状态最优解得到全局最优解，具体的解释与例子百科里就有的，有关acm了解不多，本人目前在做noip ，要说算法竞赛的提高方法也就只有A题了，可以去做做usaco之类的大题库，也可以刷刷tyvj这样的小题库，个人比较喜欢tyvj的，界面给人一种很清新的感觉做题的类型应该全面一些，动规数论图论之类的都应有涉及，好了就说这么多了.

热心网友时间：2022-06-23 17:13

DP: Dynamic Programming，即动态规划

参考资料：http://ke.baidu.com/view/416780.htm

热心网友时间：2022-06-23 17:13

额，新人
同求啊！！！！