10分求动态规划算法的形式化描述
发布网友
发布时间：2022-04-21 15:04
共1个回答
热心网友
时间：2022-05-23 16:31
使用动态规划的动机有两种，一种是利用递归的重叠子问题进行记忆化求解，这样的问题一般有比较明显的递归特性，利用递归求解后可以发现其中重叠计算的部分，利用重叠子问题转化成动态规划。还有一种是多阶段决策，所谓决策就对应着状态转移。多阶段最优决策问题也就是使得最后的转移是最优的，对于满足最优子结构和无后效性的问题，都可以分析第i
个状态到i+1状态转移的决策，而且这个决策应该是所有可以选的决策中最优的，这就是动态规划更直观的想法。
有这么一种取巧的方法，如果一个题目说明可以采用动态规划的话，而你却没有动态规划的思路，可以首先考虑用递归的方法来求解，一旦有了递归的思路来解决他，那么一定能够通过逆推求出动态规划的算法。
比如
例题1，已知两个字符串，长为L，求他们的最长的公共子串。'abacad'和'bcaaca'的最长公共子串窜就是'baca'
如果题目要求用动态规划求解，很可能根本没有思路，但是考虑用递归怎么能解决这个问题呢？
比较A[1...L]和B[1...L]这两个字符串的公共子串是不是可以变成求A[1...L-1]和B[1...L-1]的公共子串呢？貌似可以，但是好像少考虑情况了，还应该包括A[1...L]和B[1...L-1]的公共子串以及A[1...L-1]和B[1...L]这两种情况呀。这样就分析出了递归的子结构。而这个递归的子结构就是动态规划的基础。
考虑 如果A〔L〕＝＝B〔L〕那么 LCS( A[1...L] , B[1...L]) = LCS( A[1...L-1], B[1...L-1] ) + 1
否则 LCS( A[1...L] , B[1...L]) =MAX (LCS( A[1...L-1], B[1...L] )，LCS( A[1...L], B[1...L－1] ))
这样就由递推的算法得到动态规划的状态转移方程了。有了状态转移方程，动态规划算法就变成了一个添矩阵算法了，这个伪代码还是很简单的。
