华为OD笔试机试 - 园区参观路径 (Java 2024年C卷D卷真题算法)

华为OD机试（C卷+D卷）2024真题目录(Java & c++ & python)

题目描述

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

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

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

输入描述

第一行为园区的长和宽；

后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观

输出描述

输出为不同的路径数量

示例1

输入

3 3
0 0 0
0 1 0
0 0 0

输出

2

解题思路

经典动态规划问题。
我们定义dp[i][j]为从起始点到网格中位置(i,j)的所有可能路径的数量。我们需要找到一个递推关系，用更小的子问题的解来表达dp[i][j]。

这里的递推关系是基于这样一个事实：到达一个特定单元格的路径只能来自其左边的单元格或其上边的单元格。因此，到达该单元格的所有可能路径的数量就是到达其左边单元格的所有可能路径的数量和到达其上边单元格的所有可能路径的数量的和。这就是我们的递推关系。

具体来说，如果我们在第一行或第一列，那么只有一种可能的路径（沿着边缘）。所以，对于第一行和第一列，dp[i][j]就等于其左边单元格或上边单元格的dp值。对于其他位置，dp[i][j] = dp[i-1][j] + dp[i][j-1]。

这就是我们如何使用动态规划来解决这个问题的。我们首先初始化dp数组，然后使用上述递推关系来填充dp数组，最后dp[n-1][m-1]就是我们的答案，也就是从起始点到终点的所有可能路径的数量。

参考代码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt(); // 长 -> 行数
    int m = sc.nextInt(); // 宽 -> 列数

    int[][] matrix = new int[n][m]; // 地图矩阵
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    // 如果起点和终点不能参观，则没有路径
    if (matrix[0][0] == 1 || matrix[n - 1][m - 1] == 1) {
      System.out.println(0);
      return;
    }

    long[][] dp = new long[n][m];
    dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (matrix[i][j] == 1) continue;

        if (i > 0) {
          dp[i][j] += dp[i - 1][j];
        }

        if (j > 0) {
          dp[i][j] += dp[i][j - 1];
        }
      }
    }

    System.out.println(dp[n - 1][m - 1]);
  }
}