原题链接：6059. 检查是否有合法括号字符串路径



DFS参考题解：DFS 检查是否有合法括号字符串路径

class Solution {
public:
    int  v[110][110][220];
    bool dfs(vector<vector<char>>& grid,int i,int j,int s)
    {
        int m=grid.size(),n=grid[0].size();
        s+= grid[i][j]=='('? 1:-1;
        if(s<0 || s>m-i+n-j-1 ) return  false;
        if(i==m-1 && j==n-1)
        {
            if(s==0) return true;
        }
        if(v[i][j][s]) return false;
        v[i][j][s]=1;
        if(i+1<m)
        {
            if(dfs(grid,i+1,j,s)) return true;
        }
        if(j+1<n)
        {
            if(dfs(grid,i,j+1,s)) return true;
        }
        return false;
    }
    bool hasValidPath(vector<vector<char>>& grid) {
       int m=grid.size(),n=grid[0].size();
       if(grid[0][0]==')' || grid[m-1][n-1]=='(') return false;
       return dfs(grid,0,0,0);
    }
};

DP

class Solution {
public:
    
    bool hasValidPath(vector<vector<char>>& grid) {
        int m=grid.size(),n=grid[0].size();
        if(grid[0][0]==')' || grid[m-1][n-1]=='(') return false;
        vector<vector<vector<int> > > f(m,vector<vector<int>>(n,vector<int>(n+m)));
        f[0][0][1]=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n+m;k++)
                {
                    if(f[i][j][k])
                    {
                        if(i+1<m)
                        {
                            int l=k+(grid[i+1][j]=='('? 1:-1);
                            if(l>=0) f[i+1][j][l]=1;
                        }
                        if(j+1<n)
                        {
                            int l=k+(grid[i][j+1]=='('? 1:-1);
                            if(l>=0) f[i][j+1][l]=1;
                        }
                    }
                }
            }
        }
        return f[m-1][n-1][0];
    }
};