# DP solution for c++

• dp[j][i] is the solution when we are at j in s and i in p,sum[j][i] is the sum of dp[j][k] where 0<=k<=i

``````#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i<=(b);i++)
#define ROF(i,a,b) for(int i = (a);i>=(b);i--)
#define FR(i,a,b) for(int i = (a);i<(b);i++)
#define RF(i,a,b) for(int i = (a);i>(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 2005
#define M 51
#define INF 100000000000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-14
using namespace std;

int dp[2][N],sum[2][N];
class Solution {
public:
bool isMatch(string s, string p) {
int ls,lp;
ls = s.length();
lp = p.length();
if(ls == 0&&lp == 0)return 1;
MST(dp[lp&1],0);
MST(sum[lp&1],0);
dp[lp&1][ls] = 1;
sum[lp&1][ls] = 1;
for(int j = lp-1;j>=0;j--)
{
int f = (j&1);
MST(dp[f],0);
MST(sum[f],0);
for(int i = 0;i<=ls;i++)
{
if(p[j] == '?')dp[f][i] |= dp[1-f][i+1];
else if(p[j] == '*')
{
if(i>0)dp[f][i] |= (sum[1-f][ls]-sum[1-f][i-1]>0);
else dp[f][i] |= (sum[1-f][ls]>0);
}
else if(i<ls&&s[i] == p[j])dp[f][i] |= dp[1-f][i+1];

if(i == 0)sum[f][i] = dp[f][i];
else sum[f][i] = sum[f][i-1]+dp[f][i];
}
}
return dp[0][0];
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.