动态规划的题目真的越做越有意思。今天顺手把最长公共子序列的问题整理一下。
题目
典型的这类问题的形式如下：
有两个串：x和y，长度分别为m和n，求它们的最长公共子序列。
分析
我就直接从动态规划的角度来分析了。我理解的动态规划，就是从结果开始，把大问题分解成很多个小问题。
这道题也是从结果出发。
当x[m] = y[n]时，如果有一个序列是最长公共子序列，x[m]就是这个最长公共子序列的最后一个。
那么问题就转化为 x[m-1]和y[n-1] 这两个序列的 最长公共子序列长度+1。
当x[m] != y[n]时，这时候，x[m]、y[n]可能是最长公共子序列的最后一个，也可能不是。这样问题就转化为Max(x[m]与y[n-1]的最长公共子序列长度 ，x[m-1]与y[n]的最长公共子序列长度)
简单的写一个逻辑代码
dp[m][n]表示当数组x长度为m，数组y的长度为n时的最长公共子序列长度。
if(x[m] == y[n]) {
dp[m][n] = dp[m-1][n-1]；
}else{
dp[m][n] = max(dp[m][n-1],dp[m-1][n]);
}
动态规划的状态转移方程写完了，那其他的代码就很简单了，下面是一个数组的示例：
public class LCS {
public static void main(String[] args) {
int [] a ={1,3,4,7,8,9};
int [] b = {1,1,1,4,5,5,8,9};
System.out.println(longestCommonSubsequence(a,b));
}
public static int longestCommonSubsequence(int nums1[], int nums2[]) {
int result = 0;
int dp[][] = new int [nums1.length][nums2.length];
dp[0][0] = 0;
for (int i = 1;i < nums1.length;i++) {
for (int j = 1;j < nums2.length;j++) {
if (nums1[i] == nums2[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[nums1.length - 1][nums2.length - 1];
}
}
