⭐题目日期：

字节 - 2024/9/29

📖衍生：

一个矩阵如果全部为1 从头到尾路径数量数学解法

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

🌳题目描述：

给定一个二维矩阵（网格），计算从起点到终点的不同路径数量。路径从矩阵的左上角（起点）开始，到达右下角（终点）。在路径中，每次只能向下或向右移动一个位置。

🍦假设条件：

• 矩阵大小：设矩阵为 m x n 的二维数组。
• 起点和终点：
• 起点位于矩阵的左上角，坐标为 (0, 0)。
• 终点位于矩阵的右下角，坐标为 (m - 1, n - 1)。
• 移动规则：每次只能向 右 或向 下 移动一步。

📝解题思路：

• 动态规划解法：
  1. 思路：
     • 创建一个二维数组 dp，其中 dp[i] [j] 表示从起点到达位置 (i,j) 的路径数。
     • 边界条件：
       • 第一行和第一列的路径数均为 1（因为只能一直向右或向下）。
     • 状态转移方程： dp[i] [j] = dp[i−1] [j] + dp[i][j−1]
  2. 复杂度分析：
     • 时间复杂度：O(m * n)。
     • 空间复杂度：O(m * n)，可优化为 O(n)。
  3. 面试官关注点：
     • 是否能正确地初始化边界条件。
     • 是否能优化空间复杂度，例如使用一维数组。
• 递归解法（不推荐）：
  1. 思路：
     • 使用递归计算从起点到终点的路径数。
     • 由于存在大量重复计算，效率低下。
  2. 复杂度分析：
     • 时间复杂度：指数级，O(2^{m+n})。
     • 空间复杂度：递归栈的深度，O(m + n)。
  3. 面试官关注点：
     • 是否意识到递归解法的效率问题。
     • 是否能提出优化方法，如记忆化递归。
• 组合数学解法（最佳解）：

  1. 思路：

     • 机器人总共需要走 (m−1) 次向下移动和 (n−1) 次向右移动。
     • 总路径数等于这些移动的不同排列方式，即从 m+n−2 步中选择 m−1 次向下移动的组合数。

  2. 公式：

  3. 复杂度分析：

     • 时间复杂度：O(1)，如果使用高效的算法计算组合数。
     • 空间复杂度：O(1)。

  4. 面试官关注点：

     • 是否能正确推导出组合数学公式。
     • 是否考虑到大数情况下的计算，如避免整数溢出。

💻代码：

Java

 // DP 
 public int uniquePaths(int m, int n) {
     int[][] dp = new int[m][n];
     dp[0][0] = 1;
     for (int i = 0; i < m; i++) {
         for (int j = 0; j < n; j++) {
             if (i == 0 && j == 0) {
                 continue;
             }
             dp[i][j] = (i == 0 ? 0 : dp[i - 1][j]) + (j == 0 ? 0 : dp[i][j - 1]);
         }
     }
     return dp[m - 1][n - 1];
 }

Java

 // DP 空间优化 - 只使用一维数组，空间复杂度降为 O(n)。
 public int uniquePaths(int m, int n) {
     int[] dp = new int[n];
     Arrays.fill(dp, 1);
     for (int i = 1; i < m; i++) {
         for (int j = 1; j < n; j++) {
             dp[j] += dp[j - 1];
         }
     }
     return dp[n - 1];
 }

Java

 // 组合方法
 public int uniquePaths(int m, int n) {
     long result = 1;
     for (int i = 1; i < n; i++) {
         result = result * (m - 1 + i) / i;
     }
     return (int) result;
 }