【十五】【动态规划】115. 不同的子序列、44. 通配符匹配、10. 正则表达式匹配 ,三道题目深度解析

发布时间:2024年01月05日

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

115. 不同的子序列 - 力扣(LeetCode)

题目解析

状态表示

对于子序列的问题研究,我们通常研究[0,i]这段区域中的子序列的情况,对于两段字符串,研究子序列问题,我们可以分别研究一个字符串中[0,i]的区域,和另一个字符串中[0,j]的区域中的子序列的情况。

结合题目意思,我们可以定义这样的状态表示,定义dp[i][j]表示s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列个数。

状态转移方程

对于状态转移方程的推导,通常都是通过最后一个位置的状况进行分类讨论。

对(i,j)状态进行分析,尝试通过其他状态推导出(i,j)位置的状态值。

  1. 如果s[0,i]区域和t[0,j]子数组相等的子序列包括s[i]元素, 此时s[i]==s[j],要在s中[0,i]区域找和t的[0,j]子数组相等的子序列,只需要在s中[0,i-1]区域找和t的[0,j-1]子数组相等的子序列即可,在所有情况后面添加s[i]和t[j],每一种情况构成(s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列)的一种情况,此时dp[i][j]=dp[i-1][j-1]。

  2. 如果s[0,i]区域和t[0,j]子数组相等的子序列不包括s[i]元素, 此时dp[i][j]=dp[i-1][j]。

综上所述,状态转移方程为,

 
if(s[i]==t[j])dp[i][j]+=dp[i-1][j-1];
dp[i][j]+=dp[i-1][j];

因为dp[i][j]都是+=进行赋值,所以dp[i][j]一定要有初始值0,所以我们需要将所有位置的状态初始化为0。

初始化

根据状态转移方程,我们知道在推导(i,j)位置的状态时,可能需要用到(i-1,j-1)(i-1,j)位置的状态。

所以在推导蓝色位置的状态时,会发现越界情况,也就是没有前驱使得蓝色位置状态可以推导出来,所以我们需要把这些位置进行初始化。

  1. 初始化蓝色行部分, 此时i=0,j=0、1、...,我们要在[0,i]子序列中找与[0,j]相等的子序列个数。

    1. 如果[0,j]有至少两个元素, 此时dp[i][j]=0。

    2. 如果[0,j]只有一个元素, 此时dp[i][j]=s[0]==t[0]?1:0。

  2. 初始化蓝色列部分, (0,0)位置在初始化蓝色行部分就处理过了,所以我们从(0,1)开始初始化。 此时i=1、2、...,j=0,我们要在[0,i]子序列中找与[0,j]相等的子序列个数。

    ??所以我们要遍历s数组[1,i]元素,统计和t[0]相等的元素有多少个。这里需要用两个for循环,时间复杂度是O(N^2),且书写起来有些许复杂。我们希望有更简便的初始化过程。

我们在初始化过程中,觉得这个代码写起来比较复杂,我们希望可以简单实现初始化过程,因此我们可以添加虚拟节点,代替原来需要初始化位置。

即多添加一行和一列。

添加虚拟节点有几点注意事项,

  1. 对虚拟节点进行初始化,需要保证推导蓝色位置的状态的准确性。

  2. 注意下标映射的关系。

对虚拟节点进行初始化:

对虚拟节点进行初始化,一般是通过实际意义来初始化。

  1. 初始化蓝色行部分, 此时i=0,j=0、1、...,我们要在[0,i]子序列中找与[0,j]相等的子序列个数。

    1. 如果[0,j]有至少两个元素, 此时dp[i][j]=0。

    2. 如果[0,j]只有一个元素, 此时dp[i][j]=s[0]==t[0]?1:0。

  2. 初始化蓝色列部分, (0,0)位置在初始化蓝色行部分就处理过了,所以我们从(0,1)开始初始化。 此时i=1、2、...,j=0,我们要在[0,i]子序列中找与[0,j]相等的子序列个数。

      1. ??所以我们要遍历s数组[1,i]元素,统计和t[0]相等的元素有多少个。

我们先观察状态表示和状态转移方程,

dp[i][j]表示s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列个数。

if(s[i]==t[j])dp[i][j]+=dp[i-1][j-1]; dp[i][j]+=dp[i-1][j];

  1. 对蓝色行部分进行分析, 如果[0,j]有至少两个元素,即j>=1,此时dp[i][j]=0,对应状态转移方程,不管s[i]是否等于t[j],dp[i][j]都需要等于0,所以dp[i-1][j-1],dp[i-1][j]都需要初始化为0。 如果[0,j]只有一个元素,当s[i]==s[j]时,dp[i][j]=1,否则dp[i][j]=0,所以dp[i-1][j-1]应该等于1,dp[i-1][j]应该等于0。 即,(0,0)初始化为1,(0,1)、(0,2)...初始化为0。

  2. 对蓝色列部分进行分析, 此时i=1、2、...,j=0,我们要在[0,i]子序列中找与[0,j]相等的子序列个数。 dp[i][j]表示s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列个数。 if(s[i]==t[j])dp[i][j]+=dp[i-1][j-1]; dp[i][j]+=dp[i-1][j]; 如果选s[i]元素,此时s[i]==t[j],dp[i][j]+=1。 如果不选s[i]元素,dp[i][j]+=dp[i-1][j]。 对应状态转移方程,dp[i-1][j-1]应该初始化为1,dp[i-1][j]不需要处理。 即(1,0)(1,1)....全部初始化为1。

综上所述,绿色第一列全部初始化为1,第一行除第一个元素,全部初始化为0。再加上在状态转移方程中的分析,紫色位置状态全部初始化为0。

下标映射关系:

dp[i][j]表示s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列个数。

因为多添加了一行和一列,所以实际上dp[i][j]表示s中[0,i-1]区域的所有子序列,与t中[0,j-1]区域子数组相等的子序列个数。

有两种解决办法。

  1. 从dp[i][j]找s,t中对应的位置需要下标减1。即用i-1,j-1找到s,t中的对应位置。

  2. 当然也可以在s,t前面添加一个字符作为平衡,这样dp[i][j]就可以直接与s[i]、t[j]元素进行对应。

实际上下标映射关系改变后,相应的状态表示,状态转移方程都需要改变,但我们只需要注意一下下标的映射关系含义即可。

填表顺序

根据状态转移方程,

if(s[i]==t[j])dp[i][j]+=dp[i-1][j-1];
 dp[i][j]+=dp[i-1][j];

我们知道,推导(i,j)位置的状态时,我们需要用到(i-1,j-1)(i-1,j)的位置。

  1. 固定i改变j, 此时i的变化一定是从小到大,当推导 (i,)位置的状态时,(i-1,)位置的状态已经得出,所以j的变化可以从小到大,也可以从大到小。

  2. 固定j改变i, 此时j的变化一定是从小到大,又因为需要(i-1,j)位置的状态,所以i的变化也要从小到大。

返回值

根据状态表示,

dp[i][j]表示s中[0,i]区域的所有子序列,与t中[0,j]区域子数组相等的子序列个数。

结合题目意思,我们需要s中[0,m]区域的所有子序列,与t中[0,n]区域子数组相等的子序列个数。

又因为下标映射关系,所以我们需要返回dp[m][n]。

代码实现

 
class Solution {
public:
    int numDistinct(string s, string t) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = t.size(), m = s.size();
        vector<vector<double>> dp(m + 1, vector<double>(n + 1));
        for (int i = 0; i <= m; i++)
            dp[i][0] = 1; // 初始化
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                dp[i][j] += dp[i-1][j];
                if (s[i - 1] == t[j - 1])
                    dp[i][j] += dp[i - 1][j - 1];
            }
        return dp[m][n];
    }
};

44. 通配符匹配 - 力扣(LeetCode)

题目解析

状态表示

对于两个字符串之间的dp问题,我们一般的思考方式如下:

  1. 选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间当成研究对象,结合题目的要求来定义「状态表示」;

  2. 然后根据两个区间上「最后一个位置的字符」,来进行「分类讨论」,从而确定「状态转移方程」。

我们可以根据上面的策略,解决大部分关于两个字符串之间的dp问题。

因此,我们定义状态表示为: dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

状态转移方程

根据最后一个位置的具体状况进行分类讨论,

  1. 如果p[j]为一个小写英文字符,

    1. 如果p[j]==s[i], 此时只需要判断p[0,j-1]字符串能否匹配s[0,i-1]字符串,所以此时dp[i][j]=dp[i-1][j-1]。

    2. 如果p[j]!=s[i], 此时无法匹配,所以dp[i][j]=false。

  2. 如果p[j]==‘?’, 此时让p[j]==s[i],只需要判断p[0,j-1]字符串能否匹配s[0,i-1]字符串,所以此时dp[i][j]=dp[i-1][j-1]。

  3. 如果p[j]=='*',

  4. ??正常书写代码,只要一种情况可以匹配,那么dp[i][j]就等于true,所以我们要遍历dp[0][j-1]~dp[i][j-1],此时需要花费O(n)的时间,而dp表是二维,最终我们时间复杂度会达到O(n

    ??^3),我们希望可以减低时间复杂度,O(n^3)时间复杂度实在是太大了。 我们观察上述推导,可以发现一个很有趣的东西,dp[i][j-1],dp[i-1][j-1],dp[i-2][j-1]...这里横坐标很有规律的减少1,纵坐标不变。我们尝试推导dp[i-1][j],得到 dp[i-1][j]=(dp[i-1][j]||dp[i-2][j-1]||dp[i-3][j-1]||dp[i-4][j-1]....||dp[0][j-1]||j==0),又因为 dp[i][j]=(dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1].....||dp[0][j-1]||j==0),

    ??所以我们可以写成这样,dp[i][j]=(dp[i][j-1]||dp[i-1][j]) 这样用一个表达式就可以解决这一种情况,将O(n)的时间复杂度降低到了O(1)。(注意,dp[i-1][j]和dp[i][j]省略号会一直到dp[0][j-1],所以是严格相等。) 此时dp[i][j]=(dp[i][j-1]||dp[i-1][j])

将上述情况进行合并和简化,我们可以得到状态转移方程,

 
    if (p[j] == '*')
        dp[i][j] = dp[i][j-1] || dp[i-1][j];
    else
        dp[i][j] =
            (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];

初始化

根据状态转移方程,我们知道,想要推导出(i,j)位置的状态需要用到,(i,j-1)(i-1,j)(i-1,j-1)的状态。

当我们在推导蓝色部分的状态时,就会发现越界的情况,也就是没有前驱使得蓝色位置状态可以推导出来,所以我们需要把这些位置进行初始化。

为了简化初始化的过程,我们可以创建虚拟节点,即多添加一行和一列代替原先需要初始化的位置。

此时绿色部分构成原先蓝色部分的前驱,也就是代替了原先蓝色部分,我们现在只需要初始化绿色部分即可。

添加虚拟节点有几点注意事项,

  1. 对虚拟节点进行初始化,需要保证推导蓝色位置的状态的准确性。

  2. 注意下标映射的关系。

对虚拟节点进行初始化:

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

为了统一状态表示,我们可以定义绿色部分含义为空串。

dp[0][0]表示两个空串是否能匹配,此时dp[0][0]=true。

  1. 当i==0,j>0, 表示s是空串,p[0,j]能否匹配,此时如果p[0,j]全是'*',dp[i][j]=true。

  2. 当i>0,j==0, 表示p是空串,s[0,i]能否匹配,此时dp[i][j]=false。

下标映射的关系:

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

因为多添加了一行和一列,所以实际上dp[i][j]表示s中[0,i-1]区域的所有子序列,与p中[0,j-1]区域子数组相等的子序列个数。

有两种解决办法。

  1. 从dp[i][j]找s,p中对应的位置需要下标减1。即用i-1,j-1找到s,p中的对应位置。

  2. 当然也可以在s,p前面添加一个字符作为平衡,这样dp[i][j]就可以直接与s[i]、t[j]元素进行对应。

实际上下标映射关系改变后,相应的状态表示,状态转移方程都需要改变,但我们只需要注意一下下标的映射关系含义即可。

填表顺序

状态转移方程,

 
    if (p[j] == '*')
        dp[i][j] = dp[i][j-1] || dp[i-1][j];
    else
        dp[i][j] =
            (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];

根据状态转移方程,我们知道在推导(i,j)位置状态时,需要用到(i,j-1)(i-1,j)(i-1,j-1)位置的状态。

  1. 固定i,改变j, i的变化需要从小到大,由于要用到(i,j-1)位置的状态,所以j的变化需要从小到大。

  2. 固定j,改变i, j的变化需要从小到大,由于要用到(i-1,j)位置的状态,所以i的变化需要从小到大。

返回值

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

根据状态表示和题目意思,我们需要判断字符串p[0,n]能否匹配字符串 s [0,m]。

又因为下标映射关系,所以我们需要返回dp[m][n]。

代码实现

 
class Solution {
public:
    bool isMatch(string s, string p) {

        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1)); // 1. 创建 dp 表
        dp[0][0] = true;                                     // 2. 初始化
        for (int j = 1; j <= n; j++)
            if (p[j] == '*')
                dp[0][j] = true;
            else
                break;
        // 3. 填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '*')
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                else
                    dp[i][j] =
                        (p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }
};

10. 正则表达式匹配 - 力扣(LeetCode)

题目解析

状态表示

对于两个字符串之间的dp问题,我们一般的思考方式如下:

  1. 选取第一个字符串的[0,i]区间以及第二个字符串的[0,j]区间当成研究对象,结合题目的要求来定义「状态表示」;

  2. 然后根据两个区间上「最后一个位置的字符」,来进行「分类讨论」,从而确定「状态转移方程」。

我们可以根据上面的策略,解决大部分关于两个字符串之间的dp问题。

因此,我们定义状态表示为: dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

状态转移方程

根据最后一个位置的具体状况进行分类讨论,

  1. 如果p[j]为一个小写英文字母,

    1. 如果s[i]==p[j],此时dp[i][j]=dp[i-1][j-1]。

    2. 如果s[i]!=p[j],此时dp[i][j]=false。

  2. 如果p[j]=='.', 此时dp[i][j]=dp[i-1][j-1]。

  3. 如果p[j]=='*',

  4. ??观察上述推导,我们发现一个很有趣的东西,dp[i-1][j-2]、dp[i-2][j-2]、dp[i-3][j-2]....横坐标依次减一,纵坐标不变,变化十分有规律。由此我们尝试推导dp[i-1][j]的等式,得到

    ??dp[i-1][j]=(dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||...||dp[0][j-1]||全部匹配||p[i-1]=='.'),又

    ??dp[i][j]=(dp[i][j-2]||dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||...||dp[0][j-1]||全部匹配||p[i-1]=='.'),

    ??得到dp[i][j]=(dp[i][j-2]||dp[i-1][j]);

综上所述,状态转移方程为,

 
    if (p[j] == '*')
        dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
    else
        dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];

初始化

根据状态转移方程,我们知道,想要推导出(i,j)位置的状态需要用到,(i,j-2)(i-1,j)(i-1,j-1)的状态,还需要判断p[j-1]。

注意,如果*出现,前面一定有至少一个元素,所以(i,j-2)位置的状态一定不会越界。所以我们只需要考虑(i-1,j)(i-1,j-1)的状态,以及判断p[j-1]。

当我们在推导蓝色部分的状态时,就会发现越界的情况,也就是没有前驱使得蓝色位置状态可以推导出来,所以我们需要把这些位置进行初始化。

为了简化初始化的过程,我们可以创建虚拟节点,即多添加一行和一列代替原先需要初始化的位置。

添加虚拟节点有几点注意事项,

  1. 对虚拟节点进行初始化,需要保证推导蓝色位置的状态的准确性。

  2. 注意下标映射的关系。

对虚拟节点进行初始化:

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

为了统一状态表示,我们可以定义绿色部分含义为空串。

dp[0][0]表示两个空串是否能匹配,此时dp[0][0]=true。

  1. 当i==0,j>0, 表示s是空串,p[0,j]能否匹配,此时只有可能p[0,j]所有字符表示为“任一字符+*“才能匹配空串。

  2. 当i>0,j==0, 此时s[0,i],p时空串,不可能匹配,dp[i][j]=false。

下标映射的关系:

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

因为多添加了一行和一列,所以实际上dp[i][j]表示s中[0,i-1]区域的所有子序列,与p中[0,j-1]区域子数组相等的子序列个数。

有两种解决办法。

  1. 从dp[i][j]找s,p中对应的位置需要下标减1。即用i-1,j-1找到s,p中的对应位置。

  2. 当然也可以在s,p前面添加一个字符作为平衡,这样dp[i][j]就可以直接与s[i]、t[j]元素进行对应。

实际上下标映射关系改变后,相应的状态表示,状态转移方程都需要改变,但我们只需要注意一下下标的映射关系含义即可。

填表顺序

根据状态转移方程,我们知道,想要推导出(i,j)位置的状态需要用到,(i,j-2)(i-1,j)(i-1,j-1)的状态,还需要判断p[j-1]。

  1. 固定i改变j, i的变化需要从小到大,由于需要用到(i,j-2)位置的状态,所以j的变化需要从小到大。

  2. 固定j改变i, j的变化需要从小到大,由于需要用到(i-1,j)位置的状态,所以i的变化需要从小到大。

返回值

dp[i][j]表示:字符串p[0,j]能否匹配字符串 s 的[0,i]。

根据状态表示和题目意思,我们需要判断字符串p[0,n]能否匹配字符串 s [0,m]。

又因为下标映射关系,所以我们需要返回dp[m][n]。

代码实现

 
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = ' ' + s, p = ' ' + p;
        // 1. 创建 dp 表
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        // 2. 初始化
        dp[0][0] = true;
        for (int j = 2; j <= n; j += 2)
            if (p[j] == '*')
                dp[0][j] = true;
            else
                break;
        // 3. 填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j] == '*')
                    dp[i][j] =
                        dp[i][j - 2] ||
                        (p[j - 1] == '.' || p[j - 1] == s[i]) && dp[i - 1][j];
                else
                    dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j - 1];
            }
        }
        // 4. 返回值
        return dp[m][n];
    }
};

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!

文章来源:https://blog.csdn.net/m0_74163972/article/details/135416726
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。