求助Wildcard Matching

https://oj.leetcode.com/problems/wildcard-matching/
https://oj.leetcode.com/discuss/21634/c-dp-solution
上面是原题，下面是discussion里面的一种dp解法，我完全理解不了转移方程(2)。。。
按我的理解，f(i,j)应该为真当且仅当f(m,j-1)有一个为真, 0<=m<=i，但他这种做法的转移方程不仅depends on f(i,j-1), 甚至还扯上了 f(i-1,j), 这是最让我疑惑的地方。。。
谢谢各位解答！

我写过一个帖子。是贪心的做法。

http://www.1point3acres.com/bbs/thread-101201-1-1.html

Linzertorte 发表于 2015-2-25 14:46
http://www.1point3acres.com/bbs/thread-101201-1-1.html

感谢回复！
这题我已经用贪心过了，只是在看别人DP解法的时候实在理解不了转移方程于是就过来问了。

你的想法是对的，只是没有将DP贯彻到底。那个帖子中的转移方程的意思是：

如果p(1, j)在最后一个字符是'*'的情况下能够匹配s(1, i-1)，那么p(1, j)肯定也能匹配s(1, i)，因为多出来的s(i)可以由最后一个'*'匹配，这种情况下最后一个'*'匹配至少一个字符。这种情况其实已经包含了几乎所有的f(m, j-1)的情况。

但是如果p(1, j)不能匹配s(1, i-1)，那么p(1, j)很可能不能匹配s(1, i),  只有一种情况例外：就是p(1, j-1) 本身就能匹配s(1, i)，这种情况下'*'匹配0个字符。

我说你没有把DP贯彻到底的意思是：如果你已经知道了f(1, j-1)到f(i - 1, j-1)这个范围内恰有一个为真，那么现在再加上f(i, j-1)， 问你f(1, j-1)到f(i, j-1)范围内是否恰有一个为真，你完全不需要重新再去看f(1, j-1)到f(i - 1, j-1)这个范围了，而只需要检查f(i, j-1)就可以。至于之前的那个范围内是否有一个为真，你只需看f(i-1，j)就知道，因为f(i-1, j)为真是建立在f(1, j-1)到f(i-1, j)这个范围内恰有一值为真的前提上的。


上述两者只要能满足一点就说明p(1, j)能够匹配s(1, i)。

stellari 发表于 2015-2-28 14:49
你的想法是对的，只是没有将DP贯彻到底。那个帖子中的转移方程的意思是：

如果p(1, j)在最后一个字符是' ...

绕得好晕不过终于大概理解了*代表长度>0的情况了。。。

这是我头一次遇到感觉DP不如Greedy递归好理解的时候哈哈