双串DP

前言

两个串，一个模板串，一个测试串，使之“匹配” 。

如果更小规模，这里就是指两个串的前缀子串，的子问题的解决能适用贪心算法，直接被利用，计算出更大规模的问题。

正则匹配

0010 - Regular Expression Matching

简化版

0044 - Wildcard Matching

编辑距离

以莱文斯坦距离为例，对应有 LeetCode 原题： 0072 - Edit Distance 。

问题变形：

1. 有任意填充的双串问题

作为子问题的前缀子串并不是题目要求的内容，而是要进一步取舍。

Max Dot Product of Two Subsequences

代码模板

总有一个模板，利用惰性更新节省内存到一个单位的 $O(\min(n,m))$ 。

for j in 1..=m {
    let mut pre1 = cache[0];
	// init cache[0]

    for i in 1..=n {
        let pre0 = cache[i];

		// calc cache[i]

        pre1 = pre0;
    }
}

cache.pop().unwrap()

注解