1143. 最长公共子序列

【题目】给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
【分析】动态规划的思想，二维dp

  1. class Solution {
  2.     public int longestCommonSubsequence(String text1, String text2) {
  3.         int m = text1.length();
  4.         int n = text2.length();
  5.         int[][] dp = new int[m+1][n+1]; //text1[0:i)和text2[0:j)的最长公共子序列长度
  6.         for (int i=1; i<=m; i++) {
  7.             for (int j=1; j<=n; j++) {
  8.                 if (text1.charAt(i-1) == text2.charAt(j-1)) {
  9.                     dp[i][j] = dp[i-1][j-1] + 1;
  10.                 } else {
  11.                     dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
  12.                 }
  13.             }
  14.         }
  15.         return dp[m][n];
  16.     }
  17. }