题目描述补充

给定一个m x n的网格，网格中的每个格子要么是空地（用0表示），要么是障碍物（用1表示）。从左上角（(0, 0)）到右下角（(m-1, n-1)）存在多少条不同的路径？注意，每次移动只能向右或向下移动一个单位。

示例

输入:

grid = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
]

输出: 2 解释: 存在两条路径可以从左上角到达右下角，分别是(0,0) -> (0,1) -> (0,2) 和 (0,0) -> (1,0) -> (2,0) -> (2,2)。

PHP 示例代码

function uniquePaths($grid) {
    $m = count($grid);
    $n = count($grid[0]);
    
    // 初始化dp数组
    $dp = array_fill(0, $m, array_fill(0, $n, 0));
    
    // 初始化边界条件
    for ($i = 0; $i < $m; $i++) {
        $dp[$i][0] = 1;
    }
    for ($j = 0; $j < $n; $j++) {
        $dp[0][$j] = 1;
    }
    
    // 动态规划填表
    for ($i = 1; $i < $m; $i++) {
        for ($j = 1; $j < $n; $j++) {
            if ($grid[$i][$j] == 0) {
                $dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
            }
        }
    }
    
    return $dp[$m-1][$n-1];
}

// 示例用法
$grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];
echo uniquePaths($grid); // 输出: 2

Python 示例代码

def uniquePaths(grid):
    m, n = len(grid), len(grid[0])
    
    # 初始化dp数组
    dp = [[0] * n for _ in range(m)]
    
    # 初始化边界条件
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    # 动态规划填表
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

# 示例用法
grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]
print(uniquePaths(grid))  # 输出: 2

JavaScript 示例代码

function uniquePaths(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // 初始化dp数组
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    
    // 初始化边界条件
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    
    // 动态规划填表
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (grid[i][j] === 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    return dp[m-1][n-1];
}

// 示例用法
const grid = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];
console.log(uniquePaths(grid)); // 输出: 2

码小课网站中有更多相关内容分享给大家学习，欢迎访问码小课网站获取更多算法和数据结构的深入解析和实战案例。