题目

image.png

思路

  • 明确每次做动态规划的题目一定要用递归思路思考问题，如何把大问题分成小问题
  • 思路一：递归，定义recur(String text1, int i, String text2, int j)表示字符串text1前i和字符串text2前j的最大长度，每次比较我们只比较text1.charAt(i)是否等于text2.charAt(j)即可，是则加1，并且继续寻找下一个recur(text1,i+1,text2,j+1)，如果不相等我们选择recur(text1,i+1,text2,j)和recur(text1,i,text2,j+1)的最大值
  • 思路二：备忘录
  • 思路三：动态规划，基于递归
  • 思路四：优化dp数组的动态规划，基于思路三

代码

  1.     //1.暴力递归
  2.     public int longestCommonSubsequence(String text1, String text2){
  3.         return recur(text1, 0, text2, 0);
  4.     }
  6.     public int recur(String text1, int i, String text2, int j) {
  7.         if (i >= text1.length() || j >= text2.length()) return 0;
  8.         if (text1.charAt(i) == text2.charAt(j)) {
  9.             return recur(text1, i + 1, text2, j + 1) + 1;
  10.         } else {
  11.             return Math.max(recur(text1, i, text2, j + 1), recur(text1, i + 1, text2, j));
  12.         }
  13.     }
  15.     //2.备忘录
  16.     int[][] dp;
  17.     public int longestCommonSubsequence(String text1, String text2){
  18.         dp = new int[text1.length()][text2.length()];
  19.         for (int i = 0; i < text1.length(); i++) {
  20.             for (int j = 0; j < text2.length(); j++) {
  21.                 dp[i][j] = -1;
  22.             }
  23.         }
  24.         return recur(text1, 0, text2, 0);
  25.     }
  27.     public int recur(String text1, int i, String text2, int j) {
  28.         if (i >= text1.length() || j >= text2.length()) return 0;
  29.         if (dp[i][j] != -1) return dp[i][j];
  30.         int res = 0;
  31.         if (text1.charAt(i) == text2.charAt(j)) {
  32.             res = recur(text1, i + 1, text2, j + 1) + 1;
  33.         } else {
  34.             res = Math.max(recur(text1, i, text2, j + 1), recur(text1, i + 1, text2, j));
  35.         }
  36.         dp[i][j] = res;
  37.         return res;
  38.     }
  40.     //3.动态规划
  41.     public int longestCommonSubsequence(String text1, String text2) {
  42.         //dp[i][j]表示text1[0~i-1]与text2[0~j-1]的最大子序列长度，只是把备忘录的拿过来
  43.        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
  44.        for (int i = 0; i <= text1.length(); i++) {
  45.            dp[i][0] = 0;
  46.        }
  47.        for (int j = 0; j <= text2.length(); j++) {
  48.            dp[0][j] = 0;
  49.        }
  50.        for (int i = 0; i < text1.length(); i++) {
  51.            for (int j = 0; j < text2.length(); j++) {
  52.                if (text1.charAt(i) == text2.charAt(j)) {
  53.                    dp[i + 1][j + 1] = dp[i][j] + 1;
  54.                } else {
  55.                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]) ;
  56.                }
  57.            }
  58.        }
  59.        return dp[text1.length()][text2.length()];
  60.     }
  62.      //4.动态规划，优化dp数组，由于每次只用到前一列和前一个，因此可以优化为一维
  63.     public int longestCommonSubsequence(String text1, String text2) {
  64.        int[] dp = new int[text2.length() + 1];
  65.        for (int j = 0; j <= text2.length(); j++) {
  66.            dp[j] = 0;
  67.        }
  68.        for (int i = 0; i < text1.length(); i++) {
  69.            for (int j = 0, prev = dp[0]; j < text2.length(); j++) {
  70.                int t = dp[j + 1];
  71.                if (text1.charAt(i) == text2.charAt(j)) {
  72.                    dp[j + 1] = prev + 1;
  73.                } else {
  74.                    dp[j + 1] = Math.max(dp[j + 1], dp[j]) ;
  75.                }
  76.                prev = t;
  77.            }
  78.        }
  79.        return dp[text2.length()];
  80.     }

最大公共子序列