不同路径的数目(二)

[编程题]不同路径的数目(二)

热度指数：2522 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

从一个铺满字符A（中间有很多个障碍物 '#'）大小为 $n * m$ 网格的左上角走到网格的右下角（只能向右或向下走），请返回有多少不同的路径。

保证答案在 $int$ 范围内。

$1\leq n,m \leq 100$

示例1

输入

[[A,A,A],[A,#,A],[A,A,A]]

输出

说明

从左上角到右下角一共有2条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下 
2. 向下 -> 向下 -> 向右 -> 向右

示例2

输入

[[A,#,A]]

输出

说明

从左上角到右下角没有路径可以到达

算法知识视频讲解

Java

lizi-hust

import java.util.*;
public class Solution {
    public int uniquePathsWithObstacles (ArrayList<ArrayList<Integer>> obstacleGrid) {
        int m = obstacleGrid.size(), n = obstacleGrid.get(0).size();
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid.get(0).get(0);
    
        for(int i=1; i<m; i++) {
            if(obstacleGrid.get(i).get(0)==1) dp[i][0] = dp[i-1][0];
            else dp[i][0] = 0;
        }
        for(int i=1; i<n; i++) {
            if(obstacleGrid.get(0).get(i)==1) dp[0][i] = dp[0][i-1];
            else dp[0][i] = 0;
        }
        
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(obstacleGrid.get(i).get(j)==1) dp[i][j] = dp[i-1][j] + dp[i][j-1];
                else dp[i][j] = 0;
            }
        }
        return dp[m-1][n-1];
    }
}

发表于 2022-07-22 17:56:11 回复(0)