动态规划 以你之姓@ 2022-06-07 00:41 312阅读 0赞 > 给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A=”1A2C3D4B56”,B=”B1D23CA45B6A”,”123456”或者”12C4B6”都是最长公共子序列。 > > 输入输出:给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。 > > 测试样例: > “1A2C3D4B56”,10,”B1D23CA45B6A”,12 > 返回:6 代码实现: public class LCS { public int findLCS(String A, int n, String B, int m) { // write code here if(n<0||m<0||A==null||B==null){ return 0; } int dp [][] = new int[n][m]; char a[] = A.toCharArray(); char b[] = B.toCharArray(); dp[0][0]=a[0]==b[0]?1:0; for(int i = 1 ;i < n;i++){ if( a[i]==b[0] ){ dp[i][0] =1 ; }else{ dp[i][0] =dp[i-1][0]; } } for(int i =1 ;i < m;i++){ if( b[i]==a[0] ){ dp[0][i] =1 ; }else{ dp[0][i] =dp[0][i-1]; } } for(int i =1;i<n;i++){ for(int j =1;j<m;j++) { if(a[i]==b[j]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } } return dp[n-1][m-1]; } } ##### 变形: ##### > 给出两个字符串(可能包含空格),找出其中最长的公共连续子串,输出其长度。 ##### 思路: ##### > DP问题,利用空间换时间,时间复杂度O(NM),空间O(NM) > 思想: > 创建一张二维表,本来这张表是用来存储字符A\[i\]和B\[j\]是否相等然后将表中(i,j)位置置为1。 > 遍历结束后,计算所有的对角线上连续1的个数,取最大值就是结果。但是现在,换种方法, > 遍历的同时,计算当前斜对角的值,然后用一个变量res记录最大的值即可。 > 它的公式为:如果A\[i - 1\] == B\[j - 1\],那么dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1; > 其中dp\[0\]\[…\]和dp\[…\]\[0\]都是0,这是初始状态。 > 例子: > 字符串A:abcde > 字符串B:abgde > 表1 > 1 0 0 0 0 > 0 1 0 0 0 > 0 0 0 0 0 > 0 0 0 1 0 > 0 0 0 0 1 > 这个不可以直接得到结果,需要再遍历一次计算。 > > 表2 > 0 0 0 0 0 0 > 0 1 0 0 0 0 > 0 0 2 0 0 0 > 0 0 0 0 0 0 > 0 0 0 0 1 0 > 0 0 0 0 0 2 > 这个可以直接得到结果,不需要再遍历一次计算。 代码实现 import java.util.*; public class LCS { public int findLCS(String A, int n, String B, int m) { // write code here if(n<0||m<0||A==null||B==null){ return 0; } int dp [][] = new int[n][m]; char a[] = A.toCharArray(); char b[] = B.toCharArray(); int res = 0; for(int i =0;i<n;i++){ for(int j =0;j<m;j++) { if(a[i]==b[j]){ dp[i][j] = dp[i-1][j-1]+1; res = Math.max(res,dp[i][j] = dp[i - 1][j - 1] + 1); } } } return res; } }
相关 动态规划 一:概念: 和分冶法相似,不同之处在于前者是把问题划分为互不相交的子问题,而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。 基本步骤: ①:刻画一个最优 我就是我/ 2022年12月01日 11:51/ 0 赞/ 25 阅读
相关 动态规划 -------------------- 动态规划的设计思想 动态规划(DP)\[1\]通过分解成子问题解决了给定复杂的问题,并存储子问题的结果,以避免再次计算相同的结 柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 255 阅读
相关 动态规划 作者:Hawstein 出处: [http://hawstein.com/posts/dp-novice-to-advanced.html][http_hawstein.c 淡淡的烟草味﹌/ 2022年09月24日 12:17/ 0 赞/ 204 阅读
相关 动态规划 1. 首先,动态规划不是一个特定的算法,它代表的是一种思想,一种手段 2. 动态规划方法往往用于求解“最优化问题”,能用动态规划求解的问题的前提是问题具有“最优子结构性质” 刺骨的言语ヽ痛彻心扉/ 2022年07月29日 11:46/ 0 赞/ 94 阅读
相关 动态规划 首先是概念:动态规划就是将原问题划分为简单的几个小问题(有点类似与分治法?但是分治法中的各个小问题是相互独立的,彼此之间不会产生影响,但是动态规划中所得的值和前面相关,当前的解 青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 317 阅读
相关 动态规划 > 给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A=”1A2C3D4B56”,B=”B1D23CA45B6A”,”123456”或者”12C4B6”都是最 以你之姓@/ 2022年06月07日 00:41/ 0 赞/ 313 阅读
相关 动态规划 基本思想: 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 区别: 与 ゞ 浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 447 阅读
相关 动态规划 等我有时间了,一定要把《算法导论》啃完,这本书的印刷质量实在太好了,就是烧脑子,滑稽。 适合应用动态规划求解的最优化问题应该具备两个要素: 最优子结构:一个问题的最优解包含 短命女/ 2022年05月17日 09:45/ 0 赞/ 325 阅读
相关 动态规划 1.题目:最长递增子序列(Longest Increasing Subsequence) 问题描述: > 给定长度为N的数组A,计算A的最长单调递增的子序列(不一定连续) 妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 281 阅读
相关 动态规划 算法题中动态规划是真的难,写一篇总结,彻底解决动态规划。参考:[https://blog.csdn.net/u013309870/article/details/7519359 左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 494 阅读
还没有评论,来说两句吧...