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超详细白话讲解下/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

LEETCODE常见算法之动态规划DP超详细白话讲解(下)》有3条回应

  1. Pingback引用通告: LEETCODE常见算法之动态规划DP超详细白话讲解(上) - LEETCODE从零刷LEETCODE从零刷

  2. mango说:

    大大 company tag 可以更新一下嘛,比leetcoded会员少

发表评论

电子邮件地址不会被公开。