题解 | #牛牛的迷宫探索#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param maze char字符型二维数组
     * @return int整型
     */
    public int uniquePaths(char[][] maze) {
        int m = maze.length;
        int n = maze[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        // 初始化第一行
        for (int i = 1; i < n; i++) {
            if (maze[0][i] == '#') {
                break;
            }
            dp[0][i] = 1;
        }
        // 初始化第一列
        for (int j = 1; j < m; j++) {
            if (maze[j][0] == '#') {
                break;
            }
            dp[j][0] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (maze[i][j] != '#') {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.数学模拟（矩阵）

本题解题思路分析：

1.创建dp数组，每一个位置，代表从dp[0][0]开始到这个位置有多少种走法

2.先进行第一行和第一列初始化，由于dp[0][0] = 1已经初始化完毕，因此i和j从1开始

3.如果遇到#代表走不通，直接break,否则赋值为1，表示可走，有一种解法

4.遍历maze,如果遇到不是#的，计算出走到这个位置的解法，等于上+左

5.最后返回dp[m-1][n-1]，也就是数组最右下角那个位置

本题使用编程语言: Java

如果你觉得对您有帮助的话，可以点个赞，感谢~