园区参观路径 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

园区某部门举办了Family Day，邀请员工及其家属参加；

将公司园区视为一个矩形，起始园区设置在左上角，终点园区设置在右下角；

家属参观园区时，只能向右和向下园区前进，求从起始园区到终点园区会有多少条。

输入描述

输入第一行为园区的长和宽；

接下来每一行表示该园区是否可以参观，0表示可以参观，1表示不可以参观。

输出描述

输出为不同路径的数量

示例1

输入：
3 3
0 0 0
0 1 0
0 0 0

输出：
2

题解

经典的动态规划问题。

1、状态定义： dp[i][j] 表示走到格子 (i,j) 的方法数。

2、状态转移：

• 如果网格 (i,j) 上有障碍物，则 dp[i][j] 值为 0，表示走到该格子的方法数为 0；
• 否则网格 (i,j) 可以从网格 (i−1,j) 或者 网格 (i,j−1) 走过来，因此走到该格子的方法数为走到网格 (i−1,j) 和网格 (i,j−1) 的方法数之和，即 dp[i,j]=dp[i−1,j]+dp[i,j−1]。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int l = scanner.nextInt(), w = scanner.nextInt();
        int[][] garden = new int[l][w];
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < w; j++) {
                garden[i][j] = scanner.nextInt();
            }
        }

        // 初始化动态规划数组
        int[][] dp = new int[l + 1][w + 1];
        dp[0][1] = 1;

        // 动态规划计算