golang刷leetcode：检查是否有合法括号字符串路径

func hasValidPath(grid [][]byte) bool {
  m, n := len(grid), len(grid[0])
  if (m+n)%2 == 0 || grid[0][0] == ')' || grid[m-1][n-1] == '(' { // 剪枝
    return false
  }

  vis := make([][][]bool, m)
  for i := range vis {
    vis[i] = make([][]bool, n)
    for j := range vis[i] {
      vis[i][j] = make([]bool, m+n)
    }
  }
  var dfs func(x, y, c int) bool
  dfs = func(x, y, c int) bool {
    if c > m-x+n-y-1 { // 剪枝：即使后面都是 ')' 也不能将 c 减为 0
      return false
    }
    if x == m-1 && y == n-1 { // 终点
      return c == 1 // 终点一定是 ')'
    }
    if vis[x][y][c] { // 重复访问
      return false
    }
    vis[x][y][c] = true
    if grid[x][y] == '(' {
      c++
    } else if c--; c < 0 { // 非法括号字符串
      return false
    }
    return x < m-1 && dfs(x+1, y, c) || y < n-1 && dfs(x, y+1, c) // 往下或者往右
  }
  return dfs(0, 0, 0) // 起点
}

func hasValidPath(grid [][]byte) bool {
    m, n := len(grid), len(grid[0])
    if (m+n)%2 == 0 || grid[0][0] == ')' || grid[m-1][n-1] == '(' {
        return false
    }
    dp := make([][][]bool, m)
    for i := range dp {
        dp[i] = make([][]bool, n)
        for j := range dp[i] {
            dp[i][j] = make([]bool, m+n)
        }
    }
    dp[0][0][1] = true
    for i := 0; i < m; i++ {
        for j := 0; j < n; j ++ {
            t := 1
            if grid[i][j] == ')' {
                t = -1
            }
            for k := 0; k < m+n; k ++ {
                kk := k - t
                if kk < 0 || kk >= m+n{
                    continue
                }
                if i > 0 {
                    dp[i][j][k] = dp[i][j][k] || dp[i-1][j][kk]
                }
                if j > 0 {
                    dp[i][j][k] = dp[i][j][k] || dp[i][j-1][kk]
                }
            }
        }
    }
    return dp[m-1][n-1][0]
}