1. 前言

在上个章节中我们讨论了最常见的一维数组以及对应一维状态转移方程的解决方案，但是动态规划的难点在于很多情况下使用一维的状态转移方程并不能解决问题，需要使用二维甚至三维的转移方程。多维方程的状态转移函数需要抽象不同对象，例如多个字符串或者数组之间的关系。

2. 最长公共子序列

面试官提问：给定两个字符串，求解最长公共子序列。

题目解析：

求解最长公共子序列问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/longest-common-subsequence/。

首先是明确子序列的定义，例如对于字符串imooc，那么im、imo、imc都是它的子序列，子序列可以连续也可以不连续，如果是连续出现的，例如字符串imoo，一般被叫做子序列串。

其次是明确公共子序列的定义，对于两个字符串，如果包含相同的子序列，那么这个子序列就是两个字符串的公共子序列，例如imooc和moocer的公共子序列就有m和mo等，所有公共子序列中最长的子序列就是最长公共子序列（Longest Common Subsequence）。

首先从定性的角度来看，如果两个字符串中，一个字符串的长度为零，那么最长公共子序列长度一定为零。

其次从定量的角度分析这个问题，例如给定的两个字符串分别是X={x1,x2,x3 ... xm} 和Y={y1,y2,y3 ... ym}，表示X字符串是通过x1、x2一直到xm个连续字符组成，Y字符串同理。求解动态规划的通用方案是找到子问题的共性，字符串的子问题就是子字符串，我们假设X'={x1,x2,x3 ... xi} 和 Y'={y1,y2,y3 ... yi} 的最长公共子序列是L，其中i<m。那么按照递归就有两种状态转移流程：

（1）如果xi=yi，也就是两个字符串的子字符串的最后一个字符刚好相等，那么{L,x(i+1)}或者{L,y{i+1}}就是新的最长公共子序列；

（2）如果xi≠yi，也就是两个字符串的子字符串的最后一个字符并不相等，那么问题就可以转换为求下面两种情况的最长公共子序列：

第一种情况：X'={x1,x2,x3 ... x(i-1)} ，Y'={y1,y2,y3 ... yi}的最长公共子序列，假设为L1；
第二种情况：X'={x1,x2,x3 ... xi} ，Y'={y1,y2,y3 ... y(i-1)}的最长公共子序列，假设为L2。

最终需要的结果就是L = max(L1，L2)。

我们用 Java 语言实现上面描述的算法，示例：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        
        //设置dp方程初始值
        for(int i = 0; i < n+1; i++){
            for(int j = 0; j < m+1; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                }
            }
        }
        //循环更新状态
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < m+1; j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                	//如果这个位置的字符相同，说明相对于dp[i-1][j-1]刚好长一个字符
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else{
                	// 否则采用公共长度最长的
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        
        //返回结果
        return dp[n][m];
    }
}

3. 小结

本章节介绍了动态规划中最经典的最长公共子序列问题，相对于一维数组下的动态规划，二维数组的动态规划一般不能压缩空间，即时间复杂度基本都是O（n^2）的级别。字符串和动态规划结合的类似问题还有最长上升子序列、字符串的编辑距离等。候选人需要从小型数据案例开始分析状态转移的核心，问题一般都能迎刃而解。