題目

https://leetcode.com/problems/longest-common-subsequence/

題解

經典的 暴力遞歸 -> 傻緩存 -> dp 題目，以 “abcde” “ace” 為例，dp 表依賴如下：

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】DPint[][] 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);} }

總結

以上是生活随笔為你收集整理的leetcode 1143. Longest Common Subsequence | 1143. 最长公共子序列（动态规划，暴力递归-＞傻缓存-＞dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。