2267. Check if There Is a Valid Parentheses String Path

class Solution {
    public boolean hasValidPath(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (((m + n - 1) & 1) == 1) return false;
        if (grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false;
        int maxBal = (m + n - 1) / 2;
        boolean[][][] dp = new boolean[m][n][maxBal + 2];
        dp[0][0][1] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                int delta = grid[i][j] == '(' ? 1 : -1;
                for (int b = 0; b <= maxBal; b++) {
                    int prev = b - delta;
                    if (prev < 0 || prev > maxBal) continue;
                    boolean reachable = false;
                    if (i > 0 && dp[i - 1][j][prev]) reachable = true;
                    if (j > 0 && dp[i][j - 1][prev]) reachable = true;
                    if (reachable) dp[i][j][b] = true;
                }
            }
        }
        return dp[m - 1][n - 1][0];
    }
}

class Solution:
    def hasValidPath(self, grid):
        m = len(grid)
        n = len(grid[0])

        # Path length must be even
        if (m + n - 1) % 2 == 1:
            return False

        # Invalid starting or ending character
        if grid[0][0] == ')' or grid[m - 1][n - 1] == '(':
            return False

        max_bal = (m + n - 1) // 2

        dp = [
            [
                [False] * (max_bal + 2)
                for _ in range(n)
            ]
            for _ in range(m)
        ]

        # Starting '(' gives balance 1
        dp[0][0][1] = True

        for i in range(m):
            for j in range(n):

                if i == 0 and j == 0:
                    continue

                delta = 1 if grid[i][j] == '(' else -1

                for balance in range(max_bal + 1):

                    prev = balance - delta

                    if prev < 0 or prev > max_bal:
                        continue

                    reachable = False

                    # From top
                    if i > 0 and dp[i - 1][j][prev]:
                        reachable = True

                    # From left
                    if j > 0 and dp[i][j - 1][prev]:
                        reachable = True

                    if reachable:
                        dp[i][j][balance] = True

        return dp[m - 1][n - 1][0]

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {

        int m = grid.size();
        int n = grid[0].size();

        // Path length must be even
        if ((m + n - 1) % 2 == 1) {
            return false;
        }

        // Invalid starting or ending character
        if (grid[0][0] == ')' ||
            grid[m - 1][n - 1] == '(') {
            return false;
        }

        int maxBal = (m + n - 1) / 2;

        vector<vector<vector<bool>>> dp(
            m,
            vector<vector<bool>>(
                n,
                vector<bool>(maxBal + 2, false)
            )
        );

        // Starting '(' gives balance 1
        dp[0][0][1] = true;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (i == 0 && j == 0) {
                    continue;
                }

                int delta = (grid[i][j] == '(') ? 1 : -1;

                for (int balance = 0;
                     balance <= maxBal;
                     balance++) {

                    int prev = balance - delta;

                    if (prev < 0 || prev > maxBal) {
                        continue;
                    }

                    bool reachable = false;

                    // From top
                    if (i > 0 && dp[i - 1][j][prev]) {
                        reachable = true;
                    }

                    // From left
                    if (j > 0 && dp[i][j - 1][prev]) {
                        reachable = true;
                    }

                    if (reachable) {
                        dp[i][j][balance] = true;
                    }
                }
            }
        }

        return dp[m - 1][n - 1][0];
    }
};

class Solution {
    hasValidPath(grid) {

        const m = grid.length;
        const n = grid[0].length;

        // Path length must be even
        if ((m + n - 1) % 2 === 1) {
            return false;
        }

        // Invalid starting or ending character
        if (
            grid[0][0] === ')' ||
            grid[m - 1][n - 1] === '('
        ) {
            return false;
        }

        const maxBal = Math.floor((m + n - 1) / 2);

        const dp = Array.from(
            { length: m },
            () =>
                Array.from(
                    { length: n },
                    () => new Array(maxBal + 2).fill(false)
                )
        );

        // Starting '(' gives balance 1
        dp[0][0][1] = true;

        for (let i = 0; i < m; i++) {

            for (let j = 0; j < n; j++) {

                if (i === 0 && j === 0) {
                    continue;
                }

                const delta = grid[i][j] === '(' ? 1 : -1;

                for (let balance = 0;
                     balance <= maxBal;
                     balance++) {

                    const prev = balance - delta;

                    if (prev < 0 || prev > maxBal) {
                        continue;
                    }

                    let reachable = false;

                    // From top
                    if (i > 0 && dp[i - 1][j][prev]) {
                        reachable = true;
                    }

                    // From left
                    if (j > 0 && dp[i][j - 1][prev]) {
                        reachable = true;
                    }

                    if (reachable) {
                        dp[i][j][balance] = true;
                    }
                }
            }
        }

        return dp[m - 1][n - 1][0];
    }
}