动态规划：线性 DP

睡不醒的鲤鱼 2021-10-09 每日一题 LeetCode

# 0010. 正则表达式匹配 (opens new window)

题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

1
2
3

示例 2：

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

1
2
3

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

1
2
3

提示：

1 <= s.length <= 20
1 <= p.length <= 30
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

解析

代码

# 0044. 通配符匹配 (opens new window)

题目

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

解析

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j] != '*') {
                    f[i][j] = i && j && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                } else {
                    f[i][j] = (j && f[i][j - 1]) || (i && f[i - 1][j]);
                }
            }
        }
        return f[n][m];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 0053. 最大子序和 (opens new window)

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

解析

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = nums[0], ans = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            pre = pre > 0 ? pre + nums[i] : nums[i];
            ans = max(ans, pre);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11

# 0072. 编辑距离 (opens new window)

题目

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

解析

代码

class Solution {
public:
    int minDistance(string a, string b) {
        int n = a.length(), m = b.length();
        a = ' ' + a, b = ' ' + b;

        vector<vector<int>> f(n + 1, vector<int>(m + 1, INT_MAX));

        for (int i = 0; i <= n; i++) f[i][0] = i;
        for (int j = 0; j <= m; j++) f[0][j] = j;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 0097. 交错字符串 (opens new window)

题目

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

解析

定义 f(i,j) 表示 s1 的前 i 个字符和 s2 的前 j 个字符可以交错组成 s3 的前 i+j 个字符。

当 s3[i + j] = s1[i] 时，此时 f(i, j) = f(i - 1, j)；
当 s3[i + j] = s2[j] 时，此时 f(i, j) = f(i, j - 1)。

综上 f(i, j) = f(i - 1, j) || f(i, j - 1)。

代码

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length(), m = s2.length();
        if (n + m != s3.length()) return false;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        s1 = ' ' + s1, s2 = ' ' + s2, s3 = ' ' + s3;

        f[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i && s1[i] == s3[i + j]) f[i][j] = f[i - 1][j];
                if (j && s2[j] == s3[i + j]) f[i][j] = f[i][j] || f[i][j - 1];
            }
        }
        return f[n][m];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 0115. 不同的子序列 (opens new window)

题目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

解析

定义 f(i,j) 表示 s 的前 i 个字符构成的字符串的子序列中，出现的 t 的前 j 个字符构成的字符串的个数。

当 s[i] != t[j] 时，此时 f(i, j) = f(i - 1, j)；
当 s[i] != t[j] 时，此时 f(i, j) = f(i - 1, j) + f(i - 1, j - 1)。

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length(), m = t.length();

        if (!n || !m) return !n ? 0 : 1;
        if (n == m) return s == t;
        if (n < m) return 0;

        s = ' ' + s, t = ' ' + t;
        vector<vector<unsigned long long>> f(n + 1, vector<unsigned long long>(m + 1));

        for (int i = 0; i <= n; i++) f[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (s[i] == t[j]) f[i][j] += f[i - 1][j - 1];
            }
        }
        return f[n][m];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 0139. 单词拆分 (opens new window)

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

解析

定义 f(i) 表示 s 的前 i 个字符能够由字典中单词拼接构成，则 f[i] = f[j - 1] && exists(s[j...i])。

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(), wordDict.end());

        int n = s.length();
        s = ' ' + s;

        vector<bool> f(n + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j > 0; j--) {
                if (f[j - 1] && st.count(s.substr(j, i - j + 1))) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

动态规划：背包模型动态规划：区间 DP

鲤鱼笔记

Choose mode