动态规划入门必刷：不同路径 最小路径和 详解

目录

一、不同路径（中等难度）

题目描述

核心思路分析

代码实现（Java）

复杂度分析

二、最小路径和（中等难度）

题目描述

核心思路分析

代码实现（Java）

复杂度分析

三、两道题的对比与总结

四、写在最后

今天我们来啃两道经典的动态规划入门题 ——不同路径和最小路径和。它们都是网格 DP 的代表，难度中等，思路一脉相承，非常适合用来理解 “如何用动态规划解决路径问题”。下面我会用通俗的语言讲清思路、给出代码，并做优化分析，直接可以当博客发布。

一、不同路径（中等难度）

题目描述

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

核心思路分析

这道题是典型的网格路径计数 DP 问题，核心是找到递推关系：

1. 状态定义：dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数。
2. 递推公式：因为只能从上方(i-1,j)或左方(i,j-1)走到(i,j)，所以：dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 边界条件：
   • 第一行的所有点：只能从左边走过来，所以dp[0][j] = 1
   • 第一列的所有点：只能从上方走过来，所以dp[i][0] = 1
4. 优化空间：因为每一行的状态只依赖上一行和当前行左边的值，我们可以用一维数组来优化空间复杂度。

代码实现（Java）

java

运行

// 二维数组版（直观易懂） public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; // 初始化第一行 for (int j = 0; j < n; j++) { dp[0][j] = 1; } // 初始化第一列 for (int i = 0; i < m; i++) { dp[i][0] = 1; } // 递推计算 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]; } // 一维数组优化版（空间复杂度O(n)） public int uniquePathsOptimized(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++) { for (int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j-1]; } } return dp[n-1]; }

复杂度分析

• 时间复杂度：O(m * n)，遍历整个网格一次。
• 空间复杂度：
  • 二维版：O(m * n)
  • 一维优化版：O(n)（n 为列数）

二、最小路径和（中等难度）

题目描述

给定一个包含非负整数的m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

核心思路分析

这道题是上一题的 “升级版”，从计数路径数变成了求路径和的最小值，核心 DP 思想是相通的：

1. 状态定义：dp[i][j]表示从起点(0,0)走到(i,j)的最小路径和。
2. 递推公式：因为只能从上方或左方过来，所以取两者的最小值加上当前格子的值：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3. 边界条件：
   • 第一行：只能从左边来，所以dp[0][j] = dp[0][j-1] + grid[0][j]
   • 第一列：只能从上方来，所以dp[i][0] = dp[i-1][0] + grid[i][0]
4. 优化空间：同样可以用一维数组优化，甚至直接在原grid上修改，做到空间复杂度O(1)。

代码实现（Java）

java

运行

// 二维数组版（直观易懂） public int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; // 初始化第一行 for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j-1] + grid[0][j]; } // 初始化第一列 for (int i = 1; i < m; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } // 递推计算 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[m-1][n-1]; } // 原地修改版（空间复杂度O(1)） public int minPathSumInPlace(int[][] grid) { int m = grid.length; int n = grid[0].length; // 初始化第一行 for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j-1]; } // 初始化第一列 for (int i = 1; i < m; i++) { grid[i][0] += grid[i-1][0]; } // 递推计算 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1]; }

复杂度分析

• 时间复杂度：O(m * n)，遍历整个网格一次。
• 空间复杂度：
  • 二维版：O(m * n)
  • 原地修改版：O(1)（直接在原数组上操作）

三、两道题的对比与总结

表格

这两道题是网格动态规划的入门模板，它们的解题套路完全可以迁移到其他类似题目中：

1. 状态定义：通常定义dp[i][j]为到达(i,j)时的目标值（路径数、路径和、最大值等）。
2. 递推关系：根据题目允许的移动方向（只能右 / 下），找到当前状态与上一状态的关系。
3. 边界初始化：处理第一行和第一列，因为它们只能从一个方向过来。
4. 空间优化：利用滚动数组或原地修改，将空间复杂度从二维降到一维甚至常数级。

四、写在最后

刷完这两道题，你会发现动态规划的核心就是 **“大事化小，小事化了”**：把大问题拆解成一个个小的子问题，找到它们之间的递推关系，然后用空间换时间，一步步算出最终结果。