【DP】2024D-园区参观路径

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3398

题目描述

园区某部门举办了Family Day，邀请员工及其家属参加;将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；家属参观园区时，只能向右和向下园区前进；求从起始园区到终点园区会有多少条不同的参观路径

img

输入描述

第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观

1 <= 园区长, 园区宽 <= 100

输出描述

输出为不同的路径数量

示例

输入

3 3
0 0 0
0 1 0
0 0 0

输出

2

解题思路

注意，本题和LeetCode 63、不同路径 II 完全一致，属于经典的二维dp路径问题。

代码

Python

# 题目：【DP】2023C-园区参观路径
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：DP
# 代码看不懂的地方，请直接在群上提问


# 输入长n、宽m
n, m = map(int, input().split())
# 构建网格
grid = list()
for _ in range(n):
    row = list(map(int, input().split()))
    grid.append(row)

# 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
# dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
# dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
# dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
# dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
dp = [[0] * m for _ in range(n)]

# 初始化第一列的情况
for i in range(n):
    # 如果遇到障碍，则退出循环
    if grid[i][0] == 1:
        break
    # 否则记录到达点(i,0)的方法数为1种
    dp[i][0] = 1

# 初始化第一行的情况
for j in range(m):
    # 如果遇到障碍，则退出循环
    if grid[0][j] == 1:
        break
    # 否则记录到达点(0,j)的方法数为1种
    dp[0][j] = 1

# 双重循环执行dp过程
for i in range(1, n):
    for j in range(1, m):
        # 如果点(i,j)是障碍，则跳过
        if grid[i][j] == 1:
            continue
        # 否则，点(i,j)既可以从左边(i,j-1)也可以从上边(i-1,j)转移过来
        dp[i][j] = dp[i][j-1] + dp[i-1][j]

# 输出dp数组到达点(n-1,m-1)的方法数，即为达到右下角的方法数
print(dp[n-1][m-1])

Java

import java.util.Scanner;  
  
public class Main {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        int n = scanner.nextInt();  
        int m = scanner.nextInt();  
        scanner.nextLine(); // Consume the rest of the line  
  
        int[][] grid = new int[n][m];  
        int[][] dp = new int[n][m];  
  
        for (int i = 0; i < n; ++i) {  
            String[] row = scanner.nextLine().split(" ");  
            for (int j = 0; j < m; ++j) {  
                grid[i][j] = Integer.parseInt(row[j]);  
            }  
        }  
  
        for (int i = 0; i < n; ++i) {  
            if (grid[i][0] == 1) break;  
            dp[i][0] = 1;  
        }  
  
        for (int j = 0; j < m; ++j) {  
            if (grid[0][j] == 1) break;  
            dp[0][j] = 1;  
        }  
  
        for (int i = 1; i < n; ++i) {  
            for (int j = 1; j < m; ++j) {  
                if (grid[i][j] == 1) continue;  
                dp[i][j] = dp[i][j-1] + dp[i-1][j];  
            }  
        }  
  
        System.out.println(dp[n-1][m-1]);  
  
        scanner.close();  
    }  
}

C++

#include <iostream>  
#include <vector>  
  
using namespace std;  
  
int main() {  
    int n, m;  
    cin >> n >> m;  
  
    vector<vector<int>> grid(n, vector<int>(m));  
    vector<vector<int>> dp(n, vector<int>(m, 0));  
  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < m; ++j) {  
            cin >> grid[i][j];  
        }  
    }  
  
    for (int i = 0; i < n; ++i) {  
        if (grid[i][0] == 1) break;  
        dp[i][0] = 1;  
    }  
  
    for (int j = 0; j < m; ++j) {  
        if (grid[0][j] == 1) break;  
        dp[0][j] = 1;  
    }  
  
    for (int i = 1; i < n; ++i) {  
        for (int j = 1; j < m; ++j) {  
            if (grid[i][j] == 1) continue;  
            dp[i][j] = dp[i][j-1] + dp[i-1][j];  
        }  
    }  
  
    cout << dp[n-1][m-1] << endl;  
  
    return 0;  
}

时空复杂度

时间复杂度：O(NM)。dp过程中，双重循环所需时间复杂度

空间复杂度：O(NM)。二维dp数组所占空间。