漫画：最长公共子序列

显然 dp[i][j] = dp[i-1][j-1] +1 , 1 代表 i 和 j 指向的字符相等，dp[i-1][j-1] 代表除此相同字符外的 i，j 索引 之前字符串的公共子序列。

2. 当两个字符串 i，j 索引对应的字符不相等时

此时 dp[i][j] 值可能为 dp[i-1][j] 或 dp[i][j-1]， dp[i-1][j] 怎么理解，既然 i 与 j 指向的字符不等，那只要丢弃 i 字符，求  str1[0..i-1] 与 str2[0..j] 的最长公共子序列即可，即 dp[i-1][j], 同理对于dp[i][j-1]，即为丢弃 j ，求 str1[0..i] 与 str2[0..j-1] 的最长公共子序列

既然 dp[i][j] 有可能等于这两个值，那么显然应该取这两者的较大值， 

即 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 。综上可知状态状态方程如下：

阿宝的想法:

空字符串与任何字符串的最长公共子序列都为 0，所以 dp[0][i], dp[j][0] 都为 0（i

为 0 到 str1 的长度， j 为 0 到 str2 的长度）,如下图蓝色部分即为 base case。

代码如下

public class Solution {
    public static int getLCS(char[] x, char[] y) {
        // base case，以下 dp 中的每个元素默认值都为 0。
        int dp[][] = new int[x.length][y.length];
        for (int i = 1; i < x.length; i++) {
            for (int j = 1; j < y.length; j++) {
                // 以下逻辑为状态转移方程
                if (x[i] == y[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[x.length-1][y.length-1];
    }

    public static void main(String[] args) {
        char[] x =  {' ', 'a', 'b', 'c', 'e', 'f', 'g'};
        char[] y =  {' ', 'a', 'c', 'd', 'g'};
        int lcs = getLCS(x, y);
        System.out.printf("lcs = " + lcs);
    }
}

总结

对于动态规划题型，其实套路大体相似，无非就是求出 dp 方程，再自下而上的求解，对于字符串类的动态规划题型，定义好可以先画出状态转移表，然后再据此找出状态转移方程，状态转移方程的推导有一定的技巧，根据状态（比如文中 i 和 j 对应字符是否相等）可能会有不同的情况，可以多考虑下对应的字符选或不选对应的 dp 是啥，据此推导  dp 会容易一些

特别推荐一个分享架构+算法的优质内容，还没关注的小伙伴，可以长按关注一下：

长按订阅更多精彩▼

如有收获，点个在看，诚挚感谢