LC周报-动态规划(20221031-20221106)

本周做题记录

LC-44、LC-118、LC-119、LC-63、LC-72、LC-115，涉及知识点动态规划。

本周总结 1-动态规划

简介

参考《算法导论》简单介绍动态规划思想。与分治思想类似，动态规划思想也是通过组合子问题的解来推导出原问题的解，区别在于，动态规划思想中，各子问题之间存在重叠。

LC-44 通配符匹配

问题简述：给定一个字符串 (s) 和一个字符模式 (p)，'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。计算 S 和 P 是否是匹配的。

$dp[i][j]$ 表示字符串$ S$ 的前 $i$ 个字符和模式 $P$ 的前 $j$ 个字符是否能匹配根据题意可得如下的状态递推方程：

\[ dp[i][j] = \begin{cases} &(s_i == p_j) \&\& dp[i-1][j-1], \qquad &p_j\in [a-z] \\ &dp[i-1][j-1], \qquad &p_j == ?\\ &dp[i][j-1] || dp[i-1][j] \qquad &p_j == * \end{cases} \]

其中较为不容易理解的是$p_j == *$时候的情况，由于星号可以匹配 0 个或若干个任意字符，因此在匹配 0 个字符时，对应$dp[i][j-1]$的情况，匹配若干个字符时，对应$dp[i-1][j]$的情况。

另外，本题还需规定如下的初始条件：任意长度不为 0 的字符串 S 和长度为 0 的字符串 P 总是不能匹配的，因此，$dp[i][0] = false (i\neq 0)$。对于长度为 0 的字符串 S 和长度不为 0 的字符串 P，则有以下关系：

\[ dp[0][j] = \{\begin{aligned} &true & p_{1,2,...j} == *\\ &false &otherwise \end{aligned} \]

我的实现代码如下：

bool isMatch(string s, string p)
{
    int m = s.size();
    int n = p.size();
    vector<vector<bool>> f(m + 1, vector<bool>(n + 1));
    f[0][0] = true;
    for (int i = 1; i <= n; i++)
    {
        if (p[i - 1] == '*')
            f[0][i] = true;
        else
            break;
    }

    for (int i = 0; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == 0)
                break;
            if (p[j - 1] == '*')
            {
                f[i][j] = f[i - 1][j] || f[i][j - 1];
            }
            else if (p[j - 1] == '?')
            {
                f[i][j] = f[i - 1][j - 1];
            }
            else
            {
                f[i][j] = f[i - 1][j - 1] && (s[i - 1] == p[j - 1]);
            }
        }
    }
    return f[m][n];
}

LC-63 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

分析：在 A 中删除一个字符等价于在 B 中添加一个字符，在 A 中添加一个字符等价于 B 中删除一个字符，在 A 中修改一个字符与 B 中修改一个字符也等价。因此本题需要考虑的操作其实只有三种，在 A 中插入、删除、修改一个字符。针对 A 和 B，在进行 n 次操作后，只需要对 A 末尾的字符做一次修改，即可使 A、B 相等，则 A 和 B 的编辑距离为$n+1$。

我们用 $D[i][j]$ 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。则

$D[i][j]$为 A 的前 i 个字符和 B 的前$ j - 1 $个字符编辑距离的子问题。即对于 $B$ 的第$ j $个字符，我们在 A 的末尾添加了一个相同的字符，那么 $D[i][j] $最小可以为 $D[i][j-1] + 1$；

$D[i-1][j] $为 A 的前 $i - 1 $个字符和 B 的前 j 个字符编辑距离的子问题。即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么 $D[i][j]$ 最小可以为 $D[i-1][j] + 1$；

$D[i-1][j-1] $为 A 前 $i - 1$ 个字符和 B 的前 $j - 1$ 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么$D[i][j] $最小可以为 $D[i-1][j-1] + 1$。

所以，$D[i][j] = min(D[i-1][j], D[i][j-1], D[i-1][j-1])+1$，需要注意的是，若 A 和 B 最后一个字母相同，$D[i-1][j-1]$不需要加一。

实现代码如下所示：

int minDistance(string word1, string word2)
{
    int m = word1.size();
    int n = word2.size();
    vector<vector<int>> f(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= n; i++)
        f[0][i] = i;
    for (int i = 0; i <= m; i++)
        f[i][0] = i;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (word1[i - 1] == word2[j - 1])
            {
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]) + 1, f[i - 1][j - 1]);
            }
            else
            {
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
            }
        }
    }
    return f[m][n];
}

LC-115 不同的子序列

其中 dp[i][j]表示在 s[i:]的子序列中 t[j:] 出现的个数。

考虑动态规划的边界情况：当 $j=n$ 时,$t[j:]$为空字符串，由于空字符串是任何字符串的子序列，因此对任意$0≤i≤m$，有 $dp[i][n]=1$；当 $i=m$ 且 $j<n$ 时，$s[i:]$ 为空字符串，$t[j:]$为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 $0≤j<n$，有 $dp[m][j]=0$。

当$ i<m$且$ j<n$ 时，考虑 $dp[i][j]$的计算：当 $s[i]=t[j]$ 时，$dp[i][j]$ 由两部分组成：如果$s[i]$ 和$ t[j]$ 匹配，则考虑$t[j+1:]$ 作为$s[i+1:]$ 的子序列，子序列数为 $dp[i+1][j+1]$；如果 $s[i]$ 不和 $t[j]$ 匹配，则考虑 $t[j:]$ 作为 $s[i+1:]$ 的子序列，子序列数为 $dp[i+1][j]$。所以，

\[ \begin{aligned} &if \quad s[i] == t[j]:\\ &dp[i][j] = dp[i+1][j+1] + dp[i+1][j] \end{aligned} \]

同理可归纳，

\[ \begin{aligned} &if \quad s[i] \neq t[j]:\\ &dp[i][j] = dp[i+1][j] \end{aligned} \]

我的代码实现如下：

int numDistinct(string s, string t)
{

    int snum = s.size();
    int tnum = t.size();
    if (snum < tnum)
        return 0;
    vector<vector<unsigned long long>> f(snum + 1, vector<unsigned long long>(tnum + 1));
    for (int i = 0; i <= snum; i++)
        f[i][tnum] = 1;

    for (int i = snum - 1; i >= 0; i--)
    {
        for (int j = tnum - 1; j >= 0; j--)
        {
            if (s[i] == t[j])
                f[i][j] = f[i + 1][j + 1] + f[i + 1][j];
            else
                f[i][j] = f[i + 1][j];
        }
    }
    return f[0][0];
}