算法笔记 -- 经典动态规划

正则表达式

我们考虑，s和p相互匹配的过程就是两个指针i和j分别在s和p上移动。

如果最后两个指针都可以达到字符串的末尾，那么说明匹配成功，反之匹配失败。

• 如果不考虑*匹配符，只需要判断两个指针是否能达到相同的位置即可；
• 考虑*匹配符，若$s[i]==p[j]$，$p[j]$有可能需要向$s[i+\mathrm{1...}]$匹配$0$个或多个字符。
• 若$s[i]\ne p[j]$，则$p[j]$只能匹配0次，然后再看*的下一个字符是否能与$s[i]$匹配。

现在的问题就是，碰到*的时候，是应该匹配多少次？

考虑使用动态规划来解决问题。定义$dp(strings,inti,stringp,intj)$为字符串$s[i...]$是否可以匹配$p[j...]$。

class Solution {
public:
    unordered_map<string, bool> memo;
    bool isMatch(string s, string p) {
        return dp(s, 0, p, 0);
    }
    /* 计算 p[j..] 是否匹配 s[i..] */
    bool dp(string& s, int i, string& p, int j) {
        int m = s.size(), n = p.size();
        // base case
        if (j == n) {
            return i == m;
        }
        if (i == m) {
            if ((n - j) % 2 == 1) {
                return false;
            }
            for (; j + 1 < n; j += 2) {
                if (p[j + 1] != '*') {
                    return false;
                }
            }
            return true;
        }
        // 记录状态 (i, j)，消除重叠子问题
        string key = to_string(i) + "," + to_string(j);
        if (memo.count(key)) return memo[key];
        bool res = false;
        if (s[i] == p[j] || p[j] == '.') {
            if (j < n - 1 && p[j + 1] == '*') {
                // i指针不动,j指针走2步,即p与s没有匹配,选择当前字符和*的下一个字符来与s匹配
                // i指针后移,j指针不动,即p与s有匹配,所以规律串不动,s继续后移
                res = dp(s, i, p, j + 2)
                || dp(s, i + 1, p, j);
            } else {
                res = dp(s, i + 1, p, j + 1);
            }
        } else {
            if (j < n - 1 && p[j + 1] == '*') {
                // 没有匹配上就不能使用*来做通配符,而是应该直接跳过
                res = dp(s, i, p, j + 2);
            } else {
                res = false;
            }
        }
        // 将当前结果记入备忘录
        memo[key] = res;
        return res;
    }
};

四键键盘

定义$dp$函数如下：

第一个参数为剩余的按键次数，用 n 表示；第二个状态是当前屏幕上字符 A 的数量，用 a_num 表示；第三个状态是剪切板中字符 A 的数量，用 copy 表示。

结合刚才说的 4 种「选择」，我们可以把这几种选择通过状态转移表示出来：

dp(n - 1, a_num + 1, copy),    # A
解释：按下 A 键，屏幕上加一个字符
同时消耗 1 个操作数
dp(n - 1, a_num + copy, copy), # C-V
解释：按下 C-V 粘贴，剪切板中的字符加入屏幕
同时消耗 1 个操作数
dp(n - 2, a_num, a_num)        # C-A C-C
解释：全选和复制必然是联合使用的，
剪切板中 A 的数量变为屏幕上 A 的数量
同时消耗 2 个操作数

这样可以看到问题的规模 n 在不断减小，肯定可以到达 n = 0 的 base case，所以这个思路是正确的：

def maxA(N: int) -> int:
    def dp(n, a_num, copy):
        if n <= 0: return a_num;
        return max(
                dp(n - 1, a_num + 1, copy),    # A
                dp(n - 1, a_num + copy, copy), # C-V
                dp(n - 2, a_num, a_num)        # C-A C-C
            )
    # 可以按 N 次按键，屏幕和剪切板里都还没有 A
    return dp(N, 0, 0)

并且要达到最多，最后一次按键要么是A要么是Ctrl+V。

int[] dp = new int[N + 1];
// 定义：dp[i] 表示 i 次操作后最多能显示多少个 A
for (int i = 0; i <= N; i++) 
    dp[i] = max(
            这次按 A 键，
            这次按 C-V
        )

对于「按 A 键」这种情况，就是状态 i - 1 的屏幕上新增了一个 A 而已，很容易得到结果：

// 按 A 键，就比上次多一个 A 而已
dp[i] = dp[i - 1] + 1;

但是要按 C-V，还要考虑之前是在哪里 C-A C-C 的。所以最优的操作序列一定是 C-A C-C 接着若干 C-V，所以我们用一个变量 j 作为若干 C-V 的起点。那么 j 之前的 2 个操作就应该是 C-A C-C 了

public int maxA(int N) {
    int[] dp = new int[N + 1];
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        // 按 A 键
        dp[i] = dp[i - 1] + 1;
        for (int j = 2; j < i; j++) {
            // 全选 & 复制 dp[j-2]，连续粘贴 i - j 次
            // 屏幕上共 dp[j - 2] * (i - j + 1) 个 A
            dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
        }
    }
    return dp[N];
}

鸡蛋掉落

若在不限制鸡蛋个数的情况下,可以使用线性扫描或是二分的方式来查找。但是给定了鸡蛋个数N的情况下，这两种都是不可行的。

dp[k][m] = n
// m步内k个鸡蛋保证能测出n层楼

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        int m = 0;
        while (dp[K][m] < N) {
            m++;
            for (int k = 1; k <= K; k++)
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
        return m;
    }
}