华为OD机试 - 园区参观路径 - 动态规划（Java 2024 C卷 200分）

忘是亡心i 2024-04-20 12:29 1阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

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

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

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

![在这里插入图片描述][ee0c1a58d2e94d3f88719c56e77f6b96.png_pic_center]

### 二、输入描述 ###

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

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

### 三、输出描述 ###

输出为不同路径的数量。

#### 1、输入 ####

3 3  
0 0 0  
0 1 0  
0 0 0

#### 2、输出 ####

### 四、解题思路 ###

1.  读取输入的长和宽，以及园区的布局。
2.  使用动态规划的方法来计算从起始园区到终点园区的不同路径数量。
3.  初始化一个二维数组dp，其中dp\[i\]\[j\]表示从起始园区到(i, j)位置的不同路径数量。
4.  遍历整个园区，对于每个可以参观的位置(i, j)，我们可以根据其上方和左方的位置来更新dp\[i\]\[j\]的值。
5.  返回dp数组右下角的值，即为从起始园区到终点园区的不同路径数量。

### 五、Java算法源码 ###

public class Test03 {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt(); // 园区的长
            int n = sc.nextInt(); // 园区的宽
            int[][] grid = new int[m][n]; // 园区的布局
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    grid[i][j] = sc.nextInt();
                }
            }
            System.out.println(uniquePaths(grid));
        }
    
        public static int uniquePaths(int[][] grid) {
        
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n]; // 动态规划数组
    
            // 初始化第一行和第一列
            for (int i = 0; i < m; i++) {
        
                if (grid[i][0] == 0) {
        
                    dp[i][0] = 1;
                } else {
        
                    break;
                }
            }
            for (int j = 0; j < n; j++) {
        
                if (grid[0][j] == 0) {
        
                    dp[0][j] = 1;
                } else {
        
                    break;
                }
            }
    
            // 动态规划计算不同路径数量
            for (int i = 1; i < m; i++) {
        
                for (int 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];
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

5 4  
0 0 0 0  
0 1 1 0  
0 0 0 0  
0 1 1 0  
0 0 0 0

#### 2、输出 ####

![在这里插入图片描述][39bd5e28b5f54ee7b6886e8a1c3fb4fa.bmp_pic_center]

🏆下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

🏆本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c0d9c4b0460b4eac9c5d33828ced0b33.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[ee0c1a58d2e94d3f88719c56e77f6b96.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ad17b5bd70824f83b82f4eaf1fc3e79c.png
[39bd5e28b5f54ee7b6886e8a1c3fb4fa.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/39bd5e28b5f54ee7b6886e8a1c3fb4fa.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/560e7ca5e96a4fcfaccd155a8cf47ae4.gif