背景

现在整体就业行情越来越卷，不会算法题很难找到工作，之前在刷题的过程中几乎就是硬背下来的，完全不懂各种套路，找工作前刷一刷过一段时间就忘记了。有一段时间没什么需求，耐下心来系统的研究了一下各种类型题，发现几乎每一种类型题都是有套路了，只要掌握了套路大部分题读完一遍就会解题思路。

动态规划

动态规划是一种常见的算法设计思想，通常用于解决具有重叠子问题和最优子结构性质的问题。在解决动态规划问题时，可以按照以下步骤进行思考：

1. 确定状态：找出问题中的各种状态变量，通常是可以描述问题局部情况的变量。状态的设计要符合问题的要求，能够唯一确定一个子问题。
2. 确定状态转移方程：找出不同状态之间的转移关系，即如何根据已知的状态推导出新的状态。这是动态规划问题的核心，通常可以通过递推关系来描述。
3. 初始化边界条件：确定最简单的状态（通常是最小子问题）的值，作为递推的起始条件。
4. 计算顺序：根据状态转移方程和边界条件，按照一定的顺序计算各个状态的值，直到得到最终的解。
5. 最终结果：根据状态定义和转移方程，计算出整个问题的解。

在解决动态规划问题时，需要灵活运用以上思考步骤，结合具体问题的特点，不断调整和优化状态定义和状态转移方程，以求得最优解。下面根据一个题目来具体练习一下。

题目

给定两个字符串 `text1` 和 `text2`，求他们的公共子序列的长度。如果不存在公共子序列，返回 `0` 。

一个字符串的 *子序列* 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

-   例如，`ace` 是 `abcde` 的子序列，但 `aec` 不是 `abcde` 的子序列。

两个字符串的 **公共子序列** 是这两个字符串所共同拥有的子序列。

示例 1：
输入： text1 = "abcde", text2 = "ace" 
输出： 3  
解释： 最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：
输入： text1 = "abc", text2 = "abc"
输出： 3
解释： 最长公共子序列是 "abc" ，它的长度为 3 。


示例 3：
输入： text1 = "abc", text2 = "def"
输出： 0
解释： 两个字符串没有公共子序列，返回 0 。

本题是一道典型的动态规划类的问题；先思考有哪些状态或者子问题；可以从正向、反向两个方面来思考。 这里我们反向思考： 如果两个字符串str1[0 -> m]、str2[0 -> n]的最后一个字符相等，那么这两个字符串的最大子序列长度一定是str1[0 -> m-1] 和 str2[0 -> n-1]两个子串的最大子序列长度再加上相等的这个字符。 如果两个字符串str1[0 -> m]、str2[0 -> n]的最后一个字符不相等，那么会划分出来三种情况：

1. 最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m-1]、str2[0 -> n-1]的最长公共子串是一样的。
2. str2的最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m-1]、str2[0 -> n]的最长公共子串是一样的。
3. str1的最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m]、str2[0 -> n-1]的最长公共子串是一样的。

解题过程

我把解题过程拆分为6个步骤，循序渐进一步步优化，让大家知道公式是如何推出来的。

1. 根据上述子问题描述写出直接代码；
2. 通过记忆化搜索进行时间复杂度优化；
3. 转换dp数组，为进一步优化做准备；
4. 分析dp数组，进行剪枝；
5. 使用两个数组进行空间优化；
6. 使用一个数组进一步空间优化。

代码

1、根据子问题描述写出直接代码

class Solution {

    public int longestCommonSubsequence(String text1, String text2) {
        return process1(text1 , text1.length() - 1, text2 , text2.length() - 1);
    }
    
    // strs1 -> 字符串1，len1 -> 字符串1的下标。
    // strs2 -> 字符串2，len2 -> 字符串2的下标。
    private int process1(String strs1 ,int index1 , String strs2 , int index2){
        // 处理边界条件
        if(index1 < 0 || index2 < 0){
            return 0;
        }
        
        // 根据上述分析逻辑写出具体代码
        
        int result = 0;
        //同上述分析逻辑： 两个字符串str1[0 -> m]、str2[0 -> n]的最后一个字符相等，那么这两个字符串的最大子序列长度一定是str1[0 -> m-1] 和 str2[0 -> n-1]两个子串的最大子序列长度+1.
        if(strs1.charAt(index1) == strs2.charAt(index2)){
            result = process1(strs1 ,index1 -1 ,strs2 , index2 - 1) + 1;
        }else{
        
            // 最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m-1]、str2[0 -> n-1]的最长公共子串是一样的。
            int p1 = process1(strs1 ,index1 - 1 ,strs2 , index2 - 1);
            
            // str1的最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m]、str2[0 -> n-1]的最长公共子串是一样的。
            int p2 = process1(strs1 ,index1  ,strs2 , index2 - 1);
            
            // str1的最后一个字符串，不是最长公共子串中的字符，那么str1[0 -> m]、str2[0 -> n]的最长公共子串和str1[0 -> m]、str2[0 -> n-1]的最长公共子串是一样的。
            int p3 = process1(strs1 ,index1 -1 ,strs2 , index2 );
            
            // 取上述三种情况的最大值
            result = Math.max(p1, Math.max(p2,p3));
        }
        return result;
    }


}

2、记忆化搜索

对于平时写代码的平台，但凡涉及到这种题目直接根据子问题写出来的代码时间复杂度通常过高，此时我们需要分析是否有计算过的子问题，把子问题解决进行存储可以进一步降低算法的时间复杂度。这里可以看得到process方法入口中的变量只有index1、index2；而整个方法体有四个地方在递归调用，同时index1、index2的传入值有重复。有两种比较通用的方式可以进行处理，这里先介绍一种最简单的方式：记忆化搜索。

    // 用来存储之前计算出来的结果（记忆）
    Map<String,Integer> map = new HashMap();

    private int process2(String strs1 ,int index1 , String strs2 , int index2){
        // 因为变量只有index1和index2，对这两个参数组装key
        String key = index1 + "_" + index2;
        if(index1 < 0 || index2 < 0){
            return 0;
        }
        // 每次先从记忆中获取结果
        if(map.containsKey(key)){
            return map.get(key);
        }
        
        // 执行方式1原有的逻辑
        int result = 0;
        if(strs1.charAt(index1) == strs2.charAt(index2)){
            result = process2(strs1 ,index1 -1 ,strs2 , index2 - 1) + 1;
        }else{
            int p1 = process2(strs1 ,index1 - 1 ,strs2 , index2 - 1);
            int p2 = process2(strs1 ,index1  ,strs2 , index2 - 1);
            int p3 = process2(strs1 ,index1 -1 ,strs2 , index2 );
            result = Math.max(p1, Math.max(p2,p3));
        }
        // 存储记忆
        map.put(index1 + "_" + index2 , result);
        return result;
    }

根据上述存储记忆，每次先获取记忆中的结果，就可以很容易通关绝大部分类似的优化题目了。它只对原有逻辑的入口增加了map.get()方法，对出口增加了map.put()方法。

3、转换dp数组

其实从正常逻辑转换dp数组是一件非常容易的事情，只要动手写两遍就会发现其实就是把原有的代码复制了一遍，只是把result存放在dp中，每次获取结果时从dp中获取。

    
    public int longestCommonSubsequence(String text1, String text2) {
        return process3(text1 , text1.length() , text2 , text2.length());
    }
    
    // len1、len2 分别是字符串strs1、strs2的长度
    private int process3(String strs1 ,int len1 , String strs2 , int len2){
        // 原有逻辑有两个变量，说明是一个二维数组
        int[][] dp = new int[len1][len2];
        
        // 根据原有逻辑进行分析，每次都是从尾部开始往头部进行调用，说明后面的数据依赖前面的数据。
        // 此时说明index1、index2都需要从0开始
        for(int index1 = 0 ; index1 < len1 ; index1 ++){
            for(int index2 = 0 ; index2 < len2 ; index2 ++){
                
                // 直接复制原有逻辑即可。只是更改获取值从dp中获取
                int result = 0;
                if(strs1.charAt(index1) == strs2.charAt(index2)){
                    result = getValue(dp , index1 - 1 , index2 - 1) + 1;
                }else{
                    int p1 = getValue(dp , index1 - 1 , index2 - 1);
                    int p2 = getValue(dp , index1  , index2 - 1);
                    int p3 = getValue(dp , index1 - 1 , index2 );
                    result = Math.max(p1, Math.max(p2,p3));
                }
                dp[index1][index2] = result;

            }
        }
        // 返回值原有逻辑对于该方法的入参是 strs1长度-1 , strs2长度-1
        return dp[len1 - 1][len2 - 1];
    }
    
    // 处理dp数组越界的情况，和上述逻辑代码类似。
    private int getValue(int[][] dp , int i , int j){
        if(i < 0 || j < 0){
            return 0;
        }
        return dp[i][j];
    }

通过上述代码注释发现，从传统逻辑转换为dp有四个注意点:

1. 影响因素有几个就创建几维数组；
2. 下标的依赖关系，是前面影响后面还是其他种影响因素；
3. 注意dp的标界条件，默认值是什么；
4. 每次结果从dp中获取，计算结果存放在dp中。

4、对dp数组进行剪枝

这里需要对上述dp数组进行分析，我先把这个dp二维数组画出来，来分析一下他们内部元素之间的依赖关系。

这里分析(0,1)、(1,0)、（1,1）三个元素就可以很清楚我们需要剪哪些分支。上述逻辑其中当str1[index1]与str2[index2]相等时只有一个逻辑分支，这个已经没法再剪了，所以这里只分析不等的情况。

(0,1) = Math.max((0,0) , (-1,1) , (-1,0)) (1,0) = Math.max((0,0) , (0,-1) , (1,-1)) (1,1) = Math.max((0,0) , (0,1) , (1,0)) 根据1、2发现(0,1)、(1,0) >= (0,0)；所以(1,1) = Math.max((0,1) , (1,0)) 依此类推，可以把p1这种情况进行减去。

    private int process4(String strs1 ,int len1 , String strs2 , int len2){
        int[][] dp = new int[len1][len2];
        for(int index1 = 0 ; index1 < len1 ; index1 ++){
            for(int index2 = 0 ; index2 < len2 ; index2 ++){
                // 如果越界的话 就是等于0；
                int result = 0;
                if(strs1.charAt(index1) == strs2.charAt(index2)){
                    int p4 = getValue(dp , index1 - 1 , index2 - 1) + 1;
                    result = Math.max(result , p4);
                }else{
                    // 这里就是剪下去的分支
                    // int p1 = getValue(dp , index1 - 1 , index2 - 1);
                    int p2 = getValue(dp , index1  , index2 - 1);
                    int p3 = getValue(dp , index1 - 1 , index2 );
                    result = Math.max(p2,p3);
                }
                dp[index1][index2] = result;
            }
        }
        return dp[len1 - 1][len2 - 1];
    }

5、使用两个数组进行空间优化

再次分析dp数组，发现每次获取dp中的数据都是strs1的下标都只取当前index1或者index1 -1，这说明只依赖本层数据和上一层的数据，那么我们只需要维护两个数组维护好本层数据和上一层数据就可以，这种空间复杂度就可以从n*m减少到2 * Math.min(m , n)；这里可以自行实现一下。

6、使用一个数组进一步空间优化

对于分析出来使用两个数组进行空间优化从dp依赖的代码中可以很容易看出来。其实它还可以进一步分析依赖情况，首先(index1 - 1, index2 - 1)，这个依赖是不可避免的，同时需要上一层整体遍历完成才可以进行下一层的遍历赋值，此时在对当前下标赋值之前，把当前下标的值获取出来，这个值就是(index1-1,index2-1)。因为还没赋值，所以该条数据是属于上一层的数据，而需要使用时肯定是下一个index2的下标，所以该值就是(index1-1,index2-1)。代码：

    
    private int process5(String strs1 ,int len1 , String strs2 , int len2){
        // 这里还可以进行优化，取len1和len2中最小的当作该数组的长度。
        int[] dp = new int[len2];
        for(int index1 = 0 ; index1 < len1 ; index1 ++){
            // 设置初始（index1-1,index2-1）的值，因为最开始是在界限之外的。
            int pre = 0;
            for(int index2 = 0 ; index2 < len2 ; index2 ++){
                // 下面代码逻辑同上
                int result = 0;
                if(strs1.charAt(index1) == strs2.charAt(index2)){
                    int p4 = pre + 1;
                    result = Math.max(result , p4);
                }else{
                    int p2 = getValue5(dp , index2 );
                    int p3 = getValue5(dp , index2 - 1 );
                    result = Math.max(p2,p3);
                }
                pre = getValue5(dp , index2);
                dp[index2] = result;
            }
        }
        return dp[len2 - 1];
    }

    private int getValue5(int[] dp , int index){
        if(index < 0){
            return 0;
        }
        return dp[index];
    }

总结

对于动态规划、贪心类问题都可以找到一个最优子结构，通过解决这个子结构就可以把题目答案写出来，但往往直接根据子结构写的题解时间复杂度不达标，这时就需要动用一些技巧了，最简单的就是直接记忆化搜索，只需要在代码前后增加get、set方法即可，另一个种就是转换dp数组，通过dp数组进行结果缓存并且根据dp推导出来的公式可以进一步的剪枝优化。