用动态规划解决字符串问题（1）

dp[i][j]表示s的前i个字符串和p的前j个字符是否匹配，首先初始化，也就是假设s为空字符，若p的每个位置为‘*’，则匹配空字符。

后面的递推方程的话，前面一个代表i和j可以直接匹配，则dp[i][j]的值和d[i - 1][j - 1]的一样。

后面一个中，分别代表*匹配掉s中对应的字符和不匹配s中的那个字符，即对应了‘*’可以匹配也可以不匹配。

下面的图片的练习地址为https://alchemist-al.com/algorithms/wildcard-matching

import java.util.Scanner;

public class tongpeifu_pipei {

public static void main(String[] args) {

Scanner sc =new Scanner(System.in);

String s = sc.next();

String p = sc.next();

int n=s.length();

int m=p.length();

boolean[][] dp=new boolean[n+1][m+1];//固定格式必须多一行一列

        dp[0][0]=true;//初始参考值必须为true

        for(int i=1;i<=m;i++){//子串的第一个为*时跟对方的空头比肯定是true

            if(p.charAt(i-1)=='*'){

dp[0][i]=true;

}else{

break;//

            }

}

for (int i =1; i <= n; ++i) {

for (int j =1; j <= m; ++j) {

if (p.charAt(j -1) =='*') {

//如果字符为“*”就考虑他前面跟上面的的

                    dp[i][j] = dp[i][j -1] || dp[i -1][j];

}else if (p.charAt(j -1) =='?' || s.charAt(i -1) == p.charAt(j -1)) {

//如果这两个字符相等或者模式串中的为通配符“？”则看前面那个字符的匹配结果就行了。

                    dp[i][j] = dp[i -1][j -1];

}

}

}

System.out.println(dp[n][m]);

}

}

这个格式看着更容易些

https://alchemist-al.com/algorithms/wildcard-matching