我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:大丰收高手论坛 > 动态规划 >

动态规划的常用状态转移方程

归档日期:06-04       文本归类:动态规划      文章编辑:爱尚语录

  定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!NOIP2018冬令营火热报名中!

  动态规划基本会出现在信息学比赛的各类考试中,理解动态规划,学会动态规划的思想对于信息学的同学们来说至关重要!

  动态规划中当前的状态往往依赖于前一阶段的状态和前一阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui,那么第i+1阶段的状态Si+1也就确定了。所以解决动态规划问题的关键就是确定状态转移方程,一旦状态转移方程确定了,那么我们就可以根据方程式进行编码。

  对于确定状态转移方程就在第一步和第二步中,首先要确定问题的决策对象,接着对决策对象划分阶段并确定各个阶段的状态变量,最后建立各阶段的状态变量的转移方程。

  例如用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用dp[i][j]表示的两个字符串中前 i、 j 个字符的最长公共子序列,我们就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被我们称为状态。状态是描述问题当前状况的一个数字量。首先,它是数字的,是可以被抽象出来保存在内存中的。其次,它可以完全的表示一个状态的特征,而不需要其他任何的辅助信息。最后,也是状态最重要的特点,状态间的转移完全依赖于各个状态本身,如最长递增子序列中,dp[x]的值由 dp[i](i x)的值确定。若我们在分析动态规划问题的时候能够找到这样一个符合以上所有条件的状态,那么多半这个问题是可以被正确解出的。所以说,解动态规划问题的关键,就是寻找一个好的状态。

  则如果子问题的数目为O(nt),每个子问题需要用到O(ne)个子问题的结果,那么我们称它为

  (下面会把opt作为取最优值的函数(一般取min或max), w(j, i)为一个实函数,其它变量都可以在常数时间计算出来)。)

  常见于二维的迷宫问题,由于复杂度比较大,所以一般配合数据结构优化,如线段树、树状数组等。

  对于一个tD/eD 的动态规划问题,在不经过任何优化的情况下,可以粗略得到一个时间复杂度是

  O(nt+e),空间复杂度是O(nt)的算法,大多数情况下空间复杂度是很容易优化的,难点在于时间复杂度,下一章我们将详细讲解各种情况下的动态规划优化算法。

本文链接:http://quangdungfc.net/dongtaiguihua/237.html