我要投搞

标签云

收藏小站

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

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

动态规划如何去找动态转移方程

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

  兄弟连IT教育专注PHP培训,JAVA培训,大数据培训,HTML5培训,UI培训,Linux培训,python培训,云计算培训。是中国最大的移动开发高端人才教育平台,也是中国移动互联网研发人才一体化服务的领导者!

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

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

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

  因为两者的思路都是一样的,所以只给出最长递减子序列的状态转移方程。假设有序列{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]+1aiax && ix}。

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

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

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

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

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

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

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

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