专栏首页desperate633LintCode 最长公共子序列题目分析代码

LintCode 最长公共子序列题目分析代码

题目

给出两个字符串,找到最长公共子序列(LCS),返回LCS的长度。

说明 最长公共子序列的定义:

  • 最长公共子序列问题是在一组序列(通常2个)中找到最长公共子序列(注意:不同于子串,LCS不需要是连续的子串)。该问题是典型的计算机科学问题,是文件差异比较程序的基础,在生物信息学中也有所应用。
  • https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

样例

给出"ABCD" 和 "EDCA",这个LCS是 "A" (或 D或C),返回1

给出 "ABCD" 和 "EACB",这个LCS是"AC"返回 2

分析

典型的动态规划问题 dp[i][[j]:表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候: 那么显然dp[i][j] = dp[i-1][j-1] + 1,因为dp[i-1][j-1]就是前最大的情况 当A[i] != B[i]: dp[i][j] = max(dp[i][j-1],dp[i-1][j]) 初始条件很简单,显然ii,j有一个为0,dp都是0

代码

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        int n = A.length();
        int m = B.length();
        
        int[][] dp = new int[n+1][m+1];
        
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(A.charAt(i-1) == B.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
            }
        
        return dp[n][m];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LintCode 编辑距离题目分析代码

    给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。

    desperate633
  • LintCode 不同的路径题目分析代码

    有一个机器人的位于一个M×N个网格左上角(下图中标记为'Start')。 机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角(下图中标记为'F...

    desperate633
  • LintCode 背包问题I题目分析二维解法的代码优化空间复杂度代码

    在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]

    desperate633
  • 动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    Johngo
  • 穿上衣服我就不认识你了?来聊聊最长上升子序列

    最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长上升子序列。那么问题来了,它穿上衣服你还看得出来是么?

    lucifer210
  • [Leetcode][python]Triangle/三角形最小路径和

    参考:https://shenjie1993.gitbooks.io/leetcode-python/120%20Triangle.html 将一个二维数组...

    后端技术漫谈
  • Dynamic Programming - 62. Unique Paths

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

    用户5705150
  • 最长公共子串

    动态规划是大厂的热门考点,其中最长公共子串与最长公共子序列这两道题出现得尤其频繁,这两道题其实有挺多变种,很适合考察侯选人对动态规划的掌握情况,今天我们就先来看...

    kunge
  • 深入浅出理解动态规划(二) | 最优子结构

    我们在《深入浅出理解动态规划(一) | 交叠子问题》中讨论过,使用动态规划能解决的问题具有下面两个主要的性质:

    C you again
  • 动态规划此一篇就够了 万字总结

    动态规划,一直以来听着就是一种很高深莫测的算法思想。尤其是上学时候算法的第一堂课,老师巴拉巴拉列了一大堆的算法核心思想,贪心、回溯、动态规划... ...,开始...

    Johngo

扫码关注云+社区

领取腾讯云代金券