精华内容
下载资源
问答
  • 状态与状态转移方程

    千次阅读 2019-05-15 20:49:46
    状态与状态转移方程 在之前的两节中已经讨论了两类较为经典的动态规划问题的解法,本节将对两种算法进行总结,并探讨解动态规划问题的统一思路。 回顾两种经典问题的算法模式,都先定义了一个数字量,如最长递增子...

    状态与状态转移方程

    在之前的两节中已经讨论了两类较为经典的动态规划问题的解法,本节将对两种算法进行总结,并探讨解动态规划问题的统一思路。

    回顾两种经典问题的算法模式,都先定义了一个数字量,如最长递增子序列中用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用 dp[i][j]表示的两个字符串中前 i、j 个字符的最长公共子序列,就是通过对这两个数字量的不断求解最终得到答案的。这个数字量就被称为状态。

    状态是描述问题当前状况的一个数字量。首先,它是数字的,是可以被抽象出来保存在内存中的。其次,它可以完全的表示一个状态的特征,而不需要其他任何的辅助信息。最后,也是状态最重要的特点,状态间的转移完全依赖于各个状态本身,如最长递增子序列中,dp[x]的值由 dp[i](i < x)的值确定。若在分析动态规划问题的时候能够找到这样一个符合以上所有条件的状态,那么多半这个问题是可以被正确解出的。这就是为什么人们常说,做 DP 题的关键,就是寻找一个好的状态。

    将注意力放到状态的递推过程中来,由一个或多个老的状态得出一个新的状态的过程,被称为状态的转移。如最长公共子序列中,通过 dp[i - 1][j - 1]dp[i][j - 1]dp[i-1][j]的值转移得出 dp[i][j]的值就是该问题中的状态转移。而之前所说的数字量间的递推关系就被称为状态的转移规则,也被称为状态转移方程,确定状态的转移规则即确定了怎样由前序状态递推求出后续状态。如最长非递增子序列问题中的状态转移方程为:
    在这里插入图片描述
    最后来讨论动态规划问题的求解中相关时间复杂度的估计。

    以最长公共子序列为例,设两个字符串长度分别为 L1 和 L2,则共有 L1*L2个状态要求解,为了求解每个状态,按照相应字符是否相等选取 dp[i - 1][j -1] + 1 或者 max(dp[i][j - 1],dp[i - 1][j])dp[i][j]的值,即状态转移过程中每个状态的得出仅需要 O(1)的时间复杂度,所以总的时间复杂度为 O(L1 * L2 * 1)

    通过以上分析,同样也可以判断出求解最长递增子序列问题的时间复杂度构成:假设原数列长度为 n,则状态数量为 dp[n],状态转移过程中每个状态的得出复杂度平均为 O(n),所以其总的时间复杂度为 O(n*n)

    总结一下,动态规划问题的时间复杂度由两部分组成:状态数量和状态转移复杂度,往往程序总的复杂度为它们的乘积。所以说,选择一个好的状态不仅关系到程序的正确性,同时对算法的复杂度也有较大的影响,它在动态规划问题中有着举足轻重的地位。相对来说空间复杂度则没那么容易确定,可能需要额外的内存空间来辅助状态的确定和转移,也可能通过某种内存的复用提高内存的利用率。

    展开全文
  • 状态转移方程

    状态转移方程
    状态转移方程

    展开全文
  • 动态规划 dp 状态转移方程。 ACM\信息学奥赛精品资料。
  • 我们将人生划为诡异的阶段;我们把这个世界表为丰富的状态;100个常用的动态规划状态转移方程
  • 完全背包问题状态转移方程解释

    千次阅读 2018-11-12 23:45:41
    完全背包问题状态转移方程解释 这几天一直在看背包问题,看了很久才看懂完全背包问题O(VN)的算法的原理,在此记录,防止以后忘记 这是我在看了背包九讲后总结的一种思路 完全背包问题有基本思路和改进后的O(VN)算法...

    这几天一直在看背包问题,看了很久才看懂完全背包问题O(VN)的算法的原理,在此记录,防止以后忘记
    这是我在看了背包九讲后总结的一种思路


    完全背包问题有基本思路和改进后的O(VN)算法,这两个的状态转移方程基本都会出现在所有相关博客中

    基本思路

    类似于0-1背包问题,用f[i][v]表示前i种物品放入一个容量为v的背包的最大价值
    状态转移方程:

    f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}
    

    这应该容易理解,是在0-1背包问题的基础上得来的

    O(VN)算法

    f[v]来表示把N种物品放入容量为v的背包所得的最大价值

    伪代码如下:

    for v = 0 ... V do f[v] = 0
    for i = 1 ... N do
    	for v = c[i] ... V do
    		f[v] = max{f[v], f[v-c[i]] + w[i]}
    

    一种思路

    这个算法可以由前面的基本思路优化而来。
    首先,基本思路的状态转移方程可以优化为:

    f[i][v]=max{f[i-1][v], f[i][v - c[i]] + w[i]}
    

    这是因为f[i][v - c[i]] + w[i] = max{f[i-1][v - c[i] - k*c[i]] + k*w[i]} | 0 <= k*c[i] <= v-c[i]
    这可以由基本思路的状态转移方程得来。

    有了这个式子后,就容易得出O(VN)算法了,只需把空间优化成一维即可。
    另外,由于算出f[i][v]用到了第i行的值,即已被更新后的值,因此内循环要从c[i]开始遍历到V,与0-1背包问题顺序正好相反

    展开全文
  • 动态规划问题 - 经典模型的状态转移方程 状态转移方程 动态规划中当前的状态往往依赖于前一阶段的状态和前一阶段的决策结果。例如我们知道了第i个阶段的状态Si以及决策Ui,那么第i+1阶段的状态Si+1也就确定了...

    状态转移方程

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

    在前面的文章《动态规划-开篇》讲到了如何设计一个动态规划算法,有以下四个步骤:

    1、刻画一个最优解的结构特征。

    2、递归地定义最优解的值。

    3、计算最优解的值,通常采用自底向上的方法。

    4、利用计算出的信息构造一个最优解。

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

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

    总结

    下面对这几天的学习总结一下,将我遇到的各种模型的状态转移方程汇总如下:

    1、最长公共子串

    假设两个字符串为str1和str2,它们的长度分别为n和m。d[i][j]表示str1中前i个字符与str2中前j个字符分别组成的两个前缀字符串的最长公共长度。这样就把长度为n的str1和长度为m的str2划分成长度为i和长度为j的子问题进行求解。状态转移方程如下:

    1. dp[0][j] = 0; (0<=j<=m)
    2. dp[i][0] = 0; (0<=i<=n)
    3. dp[i][j] = dp[i-1][j-1] +1; (str1[i] == str2[j])
    4. dp[i][j] = 0; (str1[i] != str2[j])

    因为最长公共子串要求必须在原串中是连续的,所以一但某处出现不匹配的情况,此处的值就重置为0。

    详细代码请看最长公共子串

    2、最长公共子序列

    区分一下,最长公共子序列不同于最长公共子串,序列是保持子序列字符串的下标在str1和str2中的下标顺序是递增的,该字符串在原串中并不一定是连续的。同样的我们可以假设dp[i][j]表示为字符串str1的前i个字符和字符串str2的前j个字符的最长公共子序列的长度。状态转移方程如下:

    1. dp[0][j] = 0; (0<=j<=m)
    2. dp[i][0] = 0; (0<=i<=n)
    3. dp[i][j] = dp[i-1][j-1] +1; (str1[i-1] == str2[j-1])
    4. dp[i][j] = max{dp[i][j-1],dp[i-1][j]}; (str1[i-1] != str2[j-1])

     详细代码请看最长公共子序列

    3、最长递增子序列(最长递减子序列)

    因为两者的思路都是一样的,所以只给出最长递增子序列的状态转移方程。假设有序列{a1,a2,...,an},我们求其最长递增子序列长度。按照递推求解的思想,我们用F[i]代表若递增子序列以ai结束时它的最长长度。当 i 较小,我们容易直接得出其值,如 F[1] = 1。那么,如何由已经求得的 F[i]值推得后面的值呢?假设,F[1]到F[x-1]的值都已经确定,注意到,以ax 结尾的递增子序列,除了长度为1的情况,其它情况中,ax都是紧跟在一个由 ai(i < x)组成递增子序列之后。要求以ax结尾的最长递增子序列长度,我们依次比较 ax 与其之前所有的 ai(i < x), 若ai小于 ax,则说明ax可以跟在以ai结尾的递增子序列之后,形成一个新的递 增子序列。又因为以ai结尾的递增子序列最长长度已经求得,那么在这种情况下,由以 ai 结尾的最长递增子序列再加上 ax 得到的新的序列,其长度也可以确定,取所有这些长度的最大值,我们即能得到 F[x]的值。特殊的,当没有ai(i < x)小 于ax, 那么以 ax 结尾的递增子序列最长长度为1。 即F[x] = max{1,F[i]+1|ai<ax && i<x}。

    详细代码请看最长递增子序列

     4、最大子序列和的问题

    假设有序列{a1,a2,...,an},求子序列的和最大问题,我们用dp[i]表示以ai结尾的子序列的最大和。

    dp[1] = a1; (a1>=0 && i == 1)

    dp[i] = dp[i-1]+ai; (ai>=0 && i>=2)

    dp[i] = 0; (dp[i-1] + ai <=0 && i>=2)

    详细代码请看最大子序列的和

     5、数塔问题(动态搜索)

    给定一个数组data[n][m]构成一个数塔求从最上面走到最低端经过的路径和最大。可以假设dp[i][j]表示走到第i行第j列位置处的最大值,那么可以推出状态转移方程:

    dp[i][j] = max{dp[i-1][j-1],dp[i-1][j]} + data[i][j];

      View Code

    6、(01)背包问题

    这是一个经典的动态规划问题,另外在贪心算法里也有背包问题,至于二者的区别在此就不做介绍了。

    假设有N件物品和一个容量为V的背包。第i件物品的体积是v[i],价值是c[i],将哪些物品装入背包可使价值总和最大?

    每一种物品都有两种可能即放入背包或者不放入背包。可以用dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值,则状态转移方程可以推出如下:

    dp[i][j]=max{dp[i-1][j-v[i]]+c[i],dp[i-1][j]};

      View Code

    可以参照动态规划 - 0-1背包问题的算法优化动态规划-完全背包问题动态规划-多重背包问题

    7、矩阵连乘(矩阵链问题)-参考《算法导论》

    例如矩阵链<A1,A2,A3>,它们的维数分别为10*100,100*5,5*50,那么如果顺序相乘即((A1A2)A3),共需10*100*5 + 10*5*50 = 7500次乘法,如果按照(A1(A2A3))顺序相乘,却需做100*5*50 + 10*100*50 = 75000次乘法。两者之间相差了10倍,所以说矩阵链的相乘顺序也决定了计算量的大小。

    我们用利用动态规划的方式(dp[i][j]表示第i个矩阵至第j个矩阵这段的最优解,还有对于两个矩阵A(i,j)*B(j,k)则需要i*j*k次乘法),推出状态转移方程:

    dp[i][j] = 0; (i ==j,表示只有一个矩阵,计算次数为0)

    dp[i][j] = min{dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]}; (i<j && i<=k<j)            

    dp[1][n]即为最终求解.

      View Code

    ps

    如有错误的地方或者本人理解错的地方,请指出,共同进步!!!

    写代码是一种艺术,甚于蒙娜丽莎的微笑。

    转载于:https://www.cnblogs.com/think90/p/8455568.html

    展开全文
  • 01背包的状态转移方程

    千次阅读 2018-01-13 13:04:35
    特别是状态转移方程,记不清怎么推导的了,于是在这里做一下回顾吧 设物品个数为N,每件物品的重量为w[i],价值为v[i],背包承重W,我们用一个二维数组来表示最大收益,于是得到了方程 if w[i]>背包承重j,无法入包:...
  • 分享:神奇的动归状态转移方程——最优子序列 神奇的动归状态转移方程——最优子序列 http://my.oschina.net/llmm/blog/122946 p...
  • 老实说这道题我没有做出来,没有做出来的原因是没有定义好一个恰当的状态,当然了,就算想到了这个状态,想到状态转移方程也是另外一回事情了,就当是积累经验好了。 其实后来一想这个状态定义的确实挺好的,满足了...
  • 非常好的动态规划复习资料,有助于你提高对动态规划的理解
  • 题目链接今天刷题,本来背包问题感觉稳稳的懒得刷了,随手做两个就被卡住了,原来自己只会做死板的背包,这种稍微变形的就不会推状态转移方程了我又去看了一眼滚动背包的转变方法加上大佬的题解,才稍微明白,感觉...
  • //使用到状态转移方程 #include <cstdio> #include "algorithm" using namespace std; const int maxn =10010; int A[maxn],dp[maxn];//A存放数字序列 dp存放以A[i]结尾的连续序列最大和 int ...
  • 完全背包问题: ...可以很容易想到最基本的状态转移方程: f[i][v] = max(f[i-1][v-k*c[i]] + k*v[i]|0 &lt;= k*c[i] &lt;= v) 进一步优化,可以想到,每次求f[i][v]可以采用这样的策略:将已经...
  • 动态规划的难点就在于如何书写状态转义方程,一般来说分为以下几个步骤 确定状态,也就是原问题和子问题中变化的量。 确定dp函数的含义。比如经典的零钱兑换中,dp(n)就表示,当前的目前金额为n,至少需要dp(n)个...
  • 动态规划(一)一一状态定义和状态转移方程

    万次阅读 多人点赞 2019-09-12 10:57:56
    接下来就可以写出状态转移方程,v(i) = max(v(i - 1) + nums[i] , nums[ i ]),即下标为 i 时连续数组的最大和 肯定等于 nums[ i ] 和下标为 i - 1时连续数组的最大和 加上nums[ i ]的值中的最大的一个。...
  • 第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在
  • HDU 动态规划(46道题目)倾情奉献~ 【只提供...第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱 最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=m...
  • 状态转移方程为: 当天出行 dp[i]=min(costs[0]+dp[i-1],costs[1]+dp[i-7],costs[2]+dp[i-30])(还需额外考虑i与7,30大小) 当天不出行 dp[i]=dp[i-1] 0x03.解决代码 class Solution { public: int mincostTickets...
  • 动态规划-状态转移方程练习

    千次阅读 2019-07-23 14:17:00
    1.给定一个数组penny表示可用的...这是一个比较简单的动态规划问题,dp为状态数组,只使用1的时候有一种方法:3=1+1+1;使用1、2的时候有两种方法:3=1+1+1、3=1+2;使用1、2、4的时候因为4比3大,则还是有两种方法...
  • 最大连续子序列和 dp[i] = max(dp[i - 1] + nums[i], nums[i]) 最长上升子序列 dp[i] = max(1, dp[j] + 1) (j = 0...i - 1 && nums[j] < nums[i]) ... dp[i][j] = dp[i - 1][j - 1] ...
  • 在上一章中讲了基本的动态规划思路,但上一章中的状态转移(即小问题之间的关系)过于简单。 (上一章:https://blog.csdn.net/qq_42152365/article/details/107304816) 今天来看一道经典题: 动态规划,首先...
  • NULL
  • Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划) 目录 动态规划算法 1.1、矩阵连乘状态...
  • 1、写状态转移方程; 2、考虑初始化边界,有意义的赋定值,还没计算的赋边界值; 3、怎么写代码自底向上计算最优值 今天做了几个基础dp,全部是dp方程写对但是初始化以及计算写错 先是poj 1651 其实就是个赤裸裸的...
  • 这里说下什么是状态转移方程:从上一个状态到下一个状态之间可能存在一些变化,以及基于这些变化的最终决策结果。我们把这样的表达式称为状态转移方程。所有的动态规划算法中,状态转移是关键。 来个例子吧。 ...
  • 现在来解释一下上面这个最关键的状态转移方程! 当前背包容量为v,即将处理第i件物品。显然有如下两种方案,出现了 最优子结构 性质: a.若第i件物品加入背包,装入这前i件物品获得的最大价值F[i][v]...
  • 好吧,我想到的是枚举决策。。。  居然是个类似于区间DP的感觉。恩。。  定义状态dp[i][j][k]表示从i~j且

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 76,837
精华内容 30,734
关键字:

状态转移方程