题目大意：

有两个字符串 a、b，a字符串由大写字母和小写字母组成，b字符串除了大写字母和小写字母还有‘ * ’和‘.’。‘.’表示该字符可以变成任意字符，‘ * ’表示该字符的前一个字符可以变成任意多个，包括0个。现在问你，对于给定的两个字符串，是否可以通过对b字符串特殊字符的变换使得a字符串和b字符串完全相同。

分析：

首先假设对于两个字符串，只要不出现 ” .* “的情况，我都是可以以一种贪心的策略判断是不是能匹配的。但是因为 ” .* ” 的出现，就导致了选择的多样性，也就是说，此时，在不知道后面字符的情况下，你就没办法保证你当前的选择一定是最优的了。于是就想到了动态规划。

dp建立：

确定状态：

dp[i][j] 表示 b 字符串以标号为 i 的字符为开头的后缀是否可以与 a 字符串以标号为 j 的字符为开头的后缀匹配。

状态转移方程：

因为这个状态转移方程不好写成一个表达式，所以就用口头叙述转移过程了。
首先，外层循环 i ，内层循环 j 。对于每个 i ：
1.如果 b[ i ] 为 * ，就跳过进行下一个 i 。
2.如果 b[ i ] 不为 * ，那么就看 b[ i+1 ] 是否为 * 。
（1）如果 b[ i+1 ] 不为 * ，那么如果 dp[ i+1 ] [ j+1 ] ==1，并且a[ j ] == b[ i ] ，那么就能匹配，否则不能。
（2）如果 b[ i+1 ] 为 * ，那么，如果 dp[ i+2 ] [ j ] ==1，就能匹配。同时从 a[ j ] 开始，向前找连续的 a[ j-k ] == b[ i ] ，这些对应的dp都直接赋值为1，直到遇到一个不相等的才停止。注：如果是 “.”，就先把它赋值成 a[ j-1 ] 然后再用上述方法匹配。

确定边界条件：

这个边界条件就是打代码的时候特别难确定的。我选择的是确定b数组里哪些可以变成空，然后这些 dp[ i ][ n ]=1 表示可以和 0 个 a 字符串里的字符匹配。

代码：

#include<bits/stdc++.h>
#define maxn 2550
using namespace std;

int test;
char a[maxn],b[maxn];
bool com[maxn][maxn];
int n,m;
int main()
{
    scanf("%d",&test);
    while(test--)
    {
        memset(com,0,sizeof(com));
        scanf("%s",a);
        scanf("%s",b);
        n=strlen(a);
        m=strlen(b);
        //初始化
        com[m][n]=1;
        if(b[m-1]=='.'||b[m-1]==a[n-1])com[m-1][n-1]=1;
        for(int i=m-2;i>=0;i+=2)
        {
            if(b[i+1]=='*')com[i][n]=1;
            else break;
        }
        /*if(m-2>=0&&n-1>=0)
        {
            if(b[m-1]=='*')
            {
                for(int i=n-1;i>=0;i--)
                {
                    if(a[i]==b[m-1]||b[m-1]=='.')com[m-1][i]=1;
                    else break;
                }
            }
            else
            {
                if(n-2>=0)
                {
                    if(a[n-2]==b[m-2]||b[m-2]=='.')com[m-2][n-2]=1;
                }
            }
        }*/

        //初始化结束
        for(int i=m-1;i>=0;i--)
        {
            if(b[i]=='*')continue;
            if(b[i+1]=='*')
            {
                for(int j=n;j>=0;j--)
                {
                    if(com[i+2][j]==1)
                    {
                        com[i][j]=1;
                        if(j-1<0)continue;
                        if(b[i]=='.')b[i]=a[j-1];
                        while(a[j-1]==b[i])
                        {
                            if(j<=0)break;
                            j--;
                            com[i][j]=1;
                        }
                    }
                }
            }
            else
            {
                for(int j=n-1;j>=0;j--)
                {
                    if(com[i+1][j+1]==1)
                    {
                        if(b[i]==a[j]||b[i]=='.')com[i][j]=1;
                    }
                }
            }
        }
        /*for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                cout<<com[i][j]<<" ";
            }
            cout<<endl;
        }*/
        if(com[0][0]==1)printf("yes\n");
        else printf("no\n");
    }
}

后记：

后来看了题解的状态，是从正面开始匹配的，但是按照状态数来说，感觉这个应该还能比他的快一点常数的。