千问 LeetCode 62. 不同路径 Java实现

LeetCode 62. 不同路径是一道经典的动态规划题目。核心思路是到达某个格子的路径数等于它“上方格子”和“左方格子”的路径数之和。下面为你提供三种不同优化程度的 Java 实现从最直观到最优解法一标准二维动态规划最直观class Solution {public int uniquePaths(int m, int n) {// dp[i][j] 表示到达 (i, j) 的路径数int[][] dp new int[m][n];// 1. 初始化第一行和第一列都只有1条路径 for (int i 0; i m; i) dp[i][0] 1; for (int j 0; j n; j) dp[0][j] 1; // 2. 状态转移方程当前格子 上方 左方 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } return dp[m - 1][n - 1]; }}解法二一维数组滚动优化推荐省空间因为每次计算 dp[i][j] 只依赖上一行的 dp[i-1][j] 和当前行的 dp[i][j-1]所以可以用一维数组覆盖更新。class Solution {public int uniquePaths(int m, int n) {int[] dp new int[n];// 初始化第一行 for (int j 0; j n; j) dp[j] 1; // 从第二行开始遍历 for (int i 1; i m; i) { // 注意每行的第一个元素始终是 1所以 j 从 1 开始 for (int j 1; j n; j) { // dp[j] (未更新前) 代表上一行的值上方 // dp[j-1] (已更新) 代表当前行的值左方 dp[j] dp[j] dp[j - 1]; } } return dp[n - 1]; }}解法三数学组合公式最优时间 O(min(m,n))从左上角到右下角总共需要走 m-1 步向下n-1 步向右。总共走 mn-2 步问题等价于在这 mn-2 步中选择 m-1 步向下或 n-1 步向右的组合数。即 C(mn-2, m-1)。class Solution {public int uniquePaths(int m, int n) {long result 1;// 为了防止溢出并减少计算量取 m-1 和 n-1 中较小的那个int x Math.min(m - 1, n - 1);int y m n - 2;// 计算 C(y, x) y * (y-1) * ... * (y-x1) / x! for (int i 1; i x; i) { result result * (y - x i) / i; } return (int) result; }} 核心要点解析边界条件无论网格多大沿着最上边走和最左边走永远只有 1条 路径。状态转移机器人只能向下或向右所以 (i, j) 只能从 (i-1, j) 或 (i, j-1) 过来。空间优化解法二中 dp[j] dp[j] dp[j-1] 这一步非常精妙右边的 dp[j] 是上一层遗留下来的值dp[j-1] 是这一层刚刚算出来的值。复杂度时间复杂度O(m times n)数学法为 O(min(m, n))。空间复杂度O(n)数学法为 O(1)。如果你刚刷完这道题强烈建议紧接着做 LeetCode 63. 不同路径 II加入了障碍物只需在状态转移时加一个 if (obstacleGrid[i][j] 1) dp[j] 0; 即可