动态规划 | 您所在的位置:网站首页 › 用动态规划方法求解 › 动态规划 |
前言
动态规划是大厂的热门考点,其中最长公共子串与最长公共子序列这两道题出现得尤其频繁,这两道题其实有挺多变种,很适合考察侯选人对动态规划的掌握情况,今天我们就先来看看如何求解最长公共子串,图文并茂,清晰易懂! 最长公共子串 题目如下:输入: x = ["", "a", "b", "c", "a", "d", "f"] y = ["", "a", "c", "b", "a", "d"],输出: 2解释: 最长公共子串为 ad,所以结果为 2这里需要简单解释下子串与子序列的区别,子串要求这串字符串在原字符串中是连续的,而子序列可以不连续,两者的区别如下: 小结一下 ![]() 首先看下,如果这题如果用暴力求解的话,应该算出每个字符串的所有子字符串,然后再对所有子字符串进行比较,是个排列组合问题,时间复杂度很大,不可取!所以我们看下怎么用动态规划来解。 解动态规划需要至少明确以下三个概念 base case状态转移方程自下而上动态规划一言以蔽之就是利用 「base case 」和「状态转移方程」然后「自下而上」得求得最终问题的解。相对递归的自上而下求解造成的大量子问题的计算,自下而上意味着每个子问题不会被重复计算,很好地达到了「剪枝」的效果。这其中「状态转移方程」的求解无疑是重要的,如果求得了「状态转移」方程,问题其实就解决地差不多了。 回到最长公共子串本身来看,我们来看看它的「状态转移方程」和「base case」是啥。 1、状态转移方程这题的状态转移方程该怎么定义呢,首先我们求的是两个字符串的公共子串,所以应该意识到这个 dp 方程是个二维数组 dp[i][j],代表的 x 的前 i 个字符串与 y 的 前 j 个字符串的最长公共子串, 那么状态状态方程该怎么得出来呢,一般对于字符串类的动态规划来说,我们可以利用「状态转移表」法来帮助我们得出状态转移方程
观察出规律了吗,对于 dp[i][j] 来说,它的值有两种可能,取决于字符 x[i] 和 y[j] 这两个字符是否相等 如果两个字符相等,则 dp[i][j] = dp[i-1][j-1] + 1(注意图中的箭头), 怎么理解,1 代表 x 的第 i 个字符与 y 的第 j 个字符相等,根据 dp[i][j] 的定义,那么它自然等于 x 的前 i-1 个字符串与 y 的 前 j-1 个字符串的最长公共子串 + 1,如下图示
如果 x 的第 i 个字符与 y 的第 j 个字符不相等,那么显然 dp[i][j] = 0,因为 dp[i][j] 定义为最长公共子串,所以只要有一个字符不相等,就说明不满足最长公共子串这个定义,自然 dp[i][j] 为 0 了。 根据以上条件可知状态转移方程为: 2、base case 显然图中黄色格子所示为 base case 即可用如下公式表示 这也比较好理解,dp[0][i] 或 dp[j][0] 即空字符串与任意字符串的最大公共子串显然为0。 3、求解
这里给出C++代码(C语言代码见上图),实现了输出最长的公共子串 #include #include #include #include using namespace std; int main(){ string s1,s2; cin>>s1>>s2; if(s1.size() > s2.size()) //以短的作为s1 swap(s1,s2); int len1 = s1.size(), len2 = s2.size(); int start = 0, mx = 0; //记录结果 vector dp(len1+1,vector(len2+1,0)); for(int i = 1;i |
CopyRight 2018-2019 实验室设备网 版权所有 |