LEETCODE常见算法之动态规划DP超详细白话讲解(下)

接上文：LEETCODE常见算法之动态规划DP超详细白话讲解(上)

上一篇文章，我们使用了一道简单的例子来解释了动态规划的解题思路。本文我们来挑战一道相对复杂的问题，来对动态规划有一个更加深刻的理解。

先看例题：

---

LEETCODE 1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

---

解法一：动态规划DP

我们先考虑动态规划的解法。相对于与上一篇文章的简单问题，本题略微复杂一些。首先无论采用任何解题方式，我们要明确一点，如何有效的判断一个字符串是回文？对于这个问题，最简单的办法即是采用双指针方式，从字符串的最外侧开始，比较两端的字符是否相同，如果相同，左右指针分别向内移动一步，继续比较，直到两指针位置相邻或者相同为止。

回到动态规划的解题思路。大家是否还记得上篇文章讲过的，关于DP题目，我们需要考虑哪3件事情吗？我们一起复习一遍：

1. 将复杂问题拆分成子问题
2. 找到子问题与原问题之间的关系
3. 找到最小的子问题

本题最为复杂的问题即是「将s变成回文串需要的最少操作次数」，这是题目最终需要求解的问题，该问题我们无法一眼看出答案，因此需要将其拆分成相对简单的子问题去求解。我们举个例子来做讨论，比如题目给定的字符串为：

String s = "abcdef";

对于字符串s，我们无法一下子给出答案，因为它是一个复杂问题，复杂的关键在于它的长度太长，我们只能先去尝试解决相对简单的问题，如果此时我们能够知道它的子串s1=”bcdef”或者子串s2=”abcde”的解的话：

• f(s1) = x;
• f(s2) = y;

当我们已知将子串s1变成回文需要的步数为x时，那么对于原字符串s，s比子串s1只是在首位多出了一个字母a，这时，我们在s尾部再加上一个a，就能保证字符串s的首尾两位相同，同时中间部分子串s1的操作次数为x，因此可知将s变为回文的操作次数应该是x+1。同理，在已知将子串s2变成回文的操作次数为y的前提下，将s变成回文的操作次数应为y+1。因为题目要求最优解（操作次数最少），所以，将s变成回文的最少操作次数应该是：

f(s)=min(f(s1), f(s2))+1;

分析到这里，大家应该明白，s1和s2就是s的子问题，而他们之间的关系就是上面的公式。接下来，我们尝试将上面的公式用dp数组来代替。因为我们需要知道子串的范围，所以，dp数组需要使用二维数组来表示：

int[][] dp = new int[][];

dp[left][right]表示将原字符串区间为[left, right]的子串变成回文需要操作的最少次数，这个解应该等于：

// 其中dp[left+1][right]代表上文中的子串s1，
// dp[left][right-1]代表子串s2变成回文需要的最少操作次数
dp[left][right] = min(dp[left+1][right], dp[left][right-1])+1;

不过，我们不能忽略另外一种情况，如果当前子串两端的字符相同时，上述公式是不成立的，即当char[left]==char[right]时，我们不需要额外操作，此时dp[left][right]应该等于其内侧子串的操作次数，即：

dp[left][right] = dp[left+1][right-1];

将上述两种情况整合起来，可以表示为：

if(char[left]==char[right])
    dp[left][right] = dp[left+1][right-1];
else
    dp[left][right] = min(dp[left+1][right], dp[left][right-1])+1;

这样我们就找到了子问题与原问题之间的关系，也就是大家常说的dp推导公式。讲到这里，也许大家还会有个疑问，我们是在假设已知子串s1和s2的解的前提下推导出来的上述公式，但问题是我们现在无法得知这两个子问题的解呀！这就牵扯到我们要讨论的最后一个问题，如何找到最小子问题。

使用dp解题时，将复杂问题简单化是一个核心思想，遇到复杂问题时，先将其拆解为相对简单的子问题（例如上面的s1和s2），如果子问题仍然是复杂问题呢？继续拆呗！不过要将问题拆分到什么状态才算ok？答案是最小子问题。上一篇文章中讲过，我们对最小子问题的定义是能够直观的看出答案的问题。对于本题，如果字符串长度是0或者1，那么它一定是回文。如果长度为2，我们只要字符串中的两位元素是否相同即可。因此，最小子问题是当字符串长度小于等于2。

// left==right，长度为1的字符串本身即是回文无需操作
dp[left][right]=0;

// right-left==1，长度为2的字符串
// char[left]==char[right]，字符串本身即是回文无需操作
dp[left][right]=0;

// right-left==1，长度为2的字符串
// char[left]!=char[right],字符串本身不是回文，加上一个字符可以变成回文
// 比如ab变成aba或者变成bab
dp[left][right]=1;

到此为止，我们对本题的动态规划解法做出了分析，根据前一篇文章中所讲到的内容，我们已经知道，动态规划问题解题思路是从最简单问题开始着手，逐渐向难度更大的问题递进来解题。对于本题，也不例外，我们需要从最简单的问题开始，先得出所有长度为1的子串的解（最小问题，解都是0）。再求出所有长度为2的问题的解，最后求出长度为原字符串长度的解即可。

我们使用一个例子来模拟dp计算过程，比如字符串：

String s = "leetcode";

模拟过程：

/** dp[left][right]代表该区间内子串的解 */

// 最小子问题：长度为1的所有子串：
dp[0][0]=0;
dp[1][1]=0;
dp[2][2]=0;
dp[3][3]=0;
dp[4][4]=0;
dp[5][5]=0;
dp[6][6]=0;
dp[7][7]=0;

// 最小子问题：长度为2的所有子串：
// 查看char[left]与char[right]是否相同
// 相同时，dp值为0，不同时，dp值为1
dp[0][1]=1; // left!=right 
dp[1][2]=0; // left==right 
dp[2][3]=1; // left!=right 
dp[3][4]=1; // left!=right 
dp[4][5]=1; // left!=right 
dp[5][6]=1; // left!=right 
dp[6][7]=1; // left!=right 

// 一般子问题：长度为3的所有子串：
// 查看char[left]与char[right]是否相同
// 相同时，dp值为dp[left+1][right-1]
// 不同时，值为min(dp[left][right-1],dp[left+1][right])+1
dp[0][2]=1; // left!=right, min(dp[0][1], dp[1][2])+1
dp[1][3]=1; // left!=right, min(dp[1][2], dp[2][3])+1
dp[2][4]=2; // left!=right, min(dp[2][3], dp[3][4])+1
dp[3][5]=2; // left!=right, min(dp[3][4], dp[4][5])+1
dp[4][6]=2; // left!=right, min(dp[4][5], dp[5][6])+1
dp[5][7]=2; // left!=right, min(dp[5][6], dp[6][7])+1

// 一般子问题：长度为4的所有子串：
// dp赋值逻辑同长度3
dp[0][3]=2; // left!=right, min(dp[0][2], dp[1][3])+1
dp[1][4]=2; // left!=right, min(dp[1][3], dp[2][4])+1
dp[2][5]=3; // left!=right, min(dp[2][4], dp[3][5])+1
dp[3][6]=3; // left!=right, min(dp[3][5], dp[4][6])+1
dp[4][7]=3; // left!=right, min(dp[4][6], dp[5][7])+1

// 一般子问题：长度为5的所有子串：
// dp赋值逻辑同长度3
dp[0][4]=3; // left!=right, min(dp[0][3], dp[1][4])+1
dp[1][5]=3; // left!=right, min(dp[1][4], dp[2][5])+1
dp[2][6]=4; // left!=right, min(dp[2][5], dp[3][6])+1
dp[3][7]=4; // left!=right, min(dp[3][6], dp[4][7])+1

// 一般子问题：长度为6的所有子串：
// dp赋值逻辑同长度3
dp[0][5]=4; // left!=right, min(dp[0][4], dp[1][5])+1
dp[1][6]=4; // left!=right, min(dp[1][5], dp[2][6])+1
dp[2][7]=3; // left==right, dp[3][6]

// 一般子问题：长度为7的所有子串：
// dp赋值逻辑同长度3
dp[0][6]=5; // left!=right, min(dp[0][5], dp[1][6])+1
dp[1][7]=4; // left==right, dp[2][6]

// 最终问题：长度为8源字符串：
// dp赋值逻辑同长度3
dp[0][7]=5; // left!=right, min(dp[0][6], dp[1][7])+1

实现代码：

当dp数组为二维时，我们需要两层循环来解题，按照上面的模拟推导，我们可知，第一层循环为子串长度，因为长度为1时，dp值都为0，因此我们可以从长度2开始循环，直到字符串长度。第二层循环为子串的起始位置。循环结束后， dp[0][length-1]即是最终答案。

另外我们再复习一下dp数组，由于我们是从简单问题向复杂问题递进解题，因此，当前的中间dp解会在后面的计算中使用到，并且会不止一次被使用，比如dp[1][5]的值在计算 dp[0][5] 和 dp[1][6] 时2次被使用到，这样，使用dp数组会大大提高计算效率，减少不必要的重复计算。

public int minInsertions(String s) {
    // 初始化记忆数组
    int[][] dp =new int[s.length()][s.length()];
    // 从长度2开始循环子串长度
    for(int length=2;length<=s.length();length++){
        // 循环子串开始位置
        for(int left=0;left<s.length()-length+1;left++){
            // 子串结束位置
            int right=left+length-1;
            // 如果子串长度为2，属于最小子问题
            if(length==2){
                // 当字符相同时，无需操作，dp值为0
                if(s.charAt(left)==s.charAt(right)){
                    dp[left][right]=0;
                }else{
                // 当字符串不同时，需要添加一个字符变成回文，dp值为1
                    dp[left][right]=1;
                }
            }else if(s.charAt(left)==s.charAt(right)){
                // 当两字符相同时，dp值为内侧子串值
                dp[left][right]=dp[left+1][right-1];
            }else{
                // 两字符不同时，或者在最右侧添加一个左侧字符
                // 或者在最左侧添加一个右侧字符
                // 两者最小值为当前dp值
                dp[left][right]=Math.min(dp[left][right-1],dp[left+1][right])+1;
            }
        }
    }
    return dp[0][s.length()-1];
}

DP解题方式总结：

通过本例我们更加深入的探讨了动态规划题目的解题思路。相比上一篇文章的简单题目，本题需要使用到二维dp数组。不过解题的核心思想没有任何差别，都是尽量将复杂问题简单化，从简单到困难逐步递进解题。递进时，我们要保证当前解的子问题都已经在之前的计算中得出，不断的利用之前得出的子问题解来计算当前解，直到解出最终问题为止。

我个人认为，使用DP解题时，比较关键的点在于如何设计我们的递进方式，并有效的找出当前问题与子问题之间的关联。这也是动态规划的难点和核心。

---

动态规划的递归解释：

看过上一篇文章的话，大家已经知道所有dp题都可以转化成递归方式解题。我个人认为递归思想相比于DP思想更加简单易懂，之前的文章也多次强调过这一点，本题也不例外，如果你已经看懂了上一篇文章，那么这里，你是否可以自行使用递归方法来解出本题呢？

递归方式的解题思路可以看这篇文章：

LEETCODE 1312. Minimum Insertion Steps to Make a String Palindrome 解题思路分析

对于解题思路，上面链接的文章已经给出，这里，我们更多是想要大家明白递归与DP的关系，以便于更加深刻的理解动态规划。递归方式是完美解决子问题的方式之一。我们从最复杂的问题开始递归，通过递归子问题的解来求出当前问题的解。对于本题，递归的核心思路与上文的DP解法如出一辙，我们首先定义一个递归函数：

// arr是原字符串，为了方便使用，我们将其转化为字符数组
// l是子串左边界
// r是子串右边界
int help(char[] arr, int l, int r)

通过调用上述递归函数，help(arr, 0, length-1)即是最终答案。这也对应了DP方式中dp数组dp[0][s.length()-1]的值。

使用递归函数的话，写法上会相对简单：

int help(char[] arr, int l, int r){
    if(l>=r) return 0;
    if(memo[l][r]!=null) return memo[l][r];
    int count=0;
    if(arr[l]==arr[r]){
        count= help(arr,l+1,r-1);
    }else{
        count = Math.min(help(arr,l+1,r),help(arr,l,r-1))+1;
    }
    memo[l][r]=count;
    return count;
}

如果你已经看懂了上文的DP解法，那么对于这一段代码，你应该非常容易理解。递归函数的终止条件即是dp数组的最小子问题。而memo记忆数组则是对应了dp数组。他存在的目的也是为了防止重复计算，以提高代码的执行效率。

递归时，我们从最复杂问题开始着手，复杂问题需要的子问题的解递归到子问题去解决，原则上递归解法与DP解法的核心思想与时间复杂度完全一致。

完整实现代码：

Integer[][] memo; // 记忆数组（也可理解为dp数组）
public int minInsertions(String s) {
    // 初始化记忆数组
    memo=new Integer[s.length()][s.length()];
    // 为了提高效率，将字符串转化为数组
    char[] arr = s.toCharArray();
    // 递归求解（dp过程）
    return help(arr, 0, s.length()-1);
}
 
int help(char[] arr, int l, int r){
    // 如果区间非法，返回0
    if(l>=r) return 0;
    // 如果记忆数组存在该区间解，直接返回
    if(memo[l][r]!=null) return memo[l][r];
    // 返回结果
    int count=0;
    // 如果两指针上的字符相同
    if(arr[l]==arr[r]){
        // 左指针加一，右指针减一，递归子问题求解
        count= help(arr,l+1,r-1);
    }else{
        // 如果两指针上的字符不同
        // 此时有2中选择，或者在左边加上一个与右指针相同的字符
        // 或者在右边加上一个与左指针相同的字符
        // 两种选择的最优解为当前结果
        count = Math.min(help(arr,l+1,r),help(arr,l,r-1))+1;
    }
    // 将当前结果保存至记忆数组
    memo[l][r]=count;
    return count;
}

---

动态规划问题总结：

我们使用了两篇文章来介绍动态规划的解题思路，第一篇的例题是一道简单的重复子问题题目，本篇的难题则是解决最优子结构性质的问题。这两类问题都是动态规划DP算法的范畴，今后无论刷题时，或是面试时遇到这个类型的题目都应该首先想到使用DP（递归加记忆数组）方式来解题。如果让我用一句话来总结动态规划的核心，我认为你可以将它理解为选择综合征的解药！比如本题，一上来，你不知道怎么做能使得操作次数最少，因此你不如一一尝试，或在左边加一个字符使得它和最右边的字符相同，或者在右边加一个字符使其与最左边的字符相同，哪一种选择好，我们使用事实说话，避免了盲目选择时的忧虑。

当你遇到DP题目时，如果不能马上反应到应该使用DP算法，那只能说明你还没有了解动态规划的核心，或者你刷题数量还远远不够，这只能通过不断的练习来提高自身能力。关于本篇文章，如果你看完后还是感觉一知半解，我的建议是你先保存此文，当你刷够一定量的DP题目之后再反过来看，或许你会豁然开朗。最后祝大家刷题愉快，面试成功！

更多DP题目讲解：

动态规划相关题目解题思路分析

预告：接下来，我们还会陆续对其他经典算法做出总结，如果你想深入了解某种算法或是对某题感兴趣，都可以在文章下方留言。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode常见算法之动态规划dp超详细白话讲解下/