leetcode 1143. Longest Common Subsequence | 1143. 最长公共子序列（动态规划，暴力递归-＞傻缓存-＞dp）

た入场券 2022-09-14 06:26 161阅读 0赞

## 题目 ##

[https://leetcode.com/problems/longest-common-subsequence/][https_leetcode.com_problems_longest-common-subsequence]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

经典的 **暴力递归 -> 傻缓存 -> dp** 题目，以 “abcde” “ace” 为例，dp 表依赖如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        public int longestCommonSubsequence(String s1, String s2) { 
            // 【Solution 1】暴力递归
    // return process1(0, 0, s1, s2);
    
            // 【Solution 2】递归+傻缓存
    // int[][] dp = new int[s1.length()][s2.length()];
    // for (int[] arr : dp) { 
    // Arrays.fill(arr, -1);
    // }
    // return process2(0, 0, s1, s2, dp);
    
            // 【Solution 3】DP
            int[][] dp = new int[s1.length() + 1][s2.length() + 1];
            for (int i = s1.length() - 1; i >= 0; i--) { 
                for (int j = s2.length() - 1; j >= 0; j--) { 
                    int p1 = s1.charAt(i) == s2.charAt(j) ? dp[i + 1][j + 1] + 1 : 0;
                    int p2 = dp[i + 1][j];
                    int p3 = dp[i][j + 1];
                    dp[i][j] = Math.max(Math.max(p1, p2), p3);
                }
            }
            return dp[0][0];
        }
    
        public int process2(int i, int j, String s1, String s2, int[][] dp) { 
            if (i == s1.length() || j == s2.length()) return 0;
            if (dp[i][j] >= 0) return dp[i][j];
    
            int p1 = s1.charAt(i) == s2.charAt(j) ? process2(i + 1, j + 1, s1, s2, dp) + 1 : 0;
            int p2 = process2(i + 1, j, s1, s2, dp);
            int p3 = process2(i, j + 1, s1, s2, dp);
    
            dp[i][j] = Math.max(Math.max(p1, p2), p3);
            return dp[i][j];
        }
    
        public int process1(int i, int j, String s1, String s2) { 
            if (i == s1.length() || j == s2.length()) return 0;
            int p1 = s1.charAt(i) == s2.charAt(j) ? 1 + process1(i + 1, j + 1, s1, s2) : 0;
            int p2 = process1(i + 1, j, s1, s2);
            int p3 = process1(i, j + 1, s1, s2);
            return Math.max(Math.max(p1, p2), p3);
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_longest-common-subsequence]: https://leetcode.com/problems/longest-common-subsequence/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ce3a3f98d9ba4055ae3aff6700fed13f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/bfc20f986bb248289d9922bd69dfc325.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/45b17420895140919b2b086ad7625e45.png