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

目录一、不同路径中等难度题目描述核心思路分析代码实现Java复杂度分析二、最小路径和中等难度题目描述核心思路分析代码实现Java复杂度分析三、两道题的对比与总结四、写在最后今天我们来啃两道经典的动态规划入门题 ——不同路径和最小路径和。它们都是网格 DP 的代表难度中等思路一脉相承非常适合用来理解 “如何用动态规划解决路径问题”。下面我会用通俗的语言讲清思路、给出代码并做优化分析直接可以当博客发布。一、不同路径中等难度题目描述一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径核心思路分析这道题是典型的网格路径计数 DP 问题核心是找到递推关系状态定义dp[i][j]表示从起点(0,0)走到(i,j)的不同路径数。递推公式因为只能从上方(i-1,j)或左方(i,j-1)走到(i,j)所以dp[i][j] dp[i-1][j] dp[i][j-1]边界条件第一行的所有点只能从左边走过来所以dp[0][j] 1第一列的所有点只能从上方走过来所以dp[i][0] 1优化空间因为每一行的状态只依赖上一行和当前行左边的值我们可以用一维数组来优化空间复杂度。代码实现Javajava运行// 二维数组版直观易懂 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 思想是相通的状态定义dp[i][j]表示从起点(0,0)走到(i,j)的最小路径和。递推公式因为只能从上方或左方过来所以取两者的最小值加上当前格子的值dp[i][j] Math.min(dp[i-1][j], dp[i][j-1]) grid[i][j]边界条件第一行只能从左边来所以dp[0][j] dp[0][j-1] grid[0][j]第一列只能从上方来所以dp[i][0] dp[i-1][0] grid[i][0]优化空间同样可以用一维数组优化甚至直接在原grid上修改做到空间复杂度O(1)。代码实现Javajava运行// 二维数组版直观易懂 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)直接在原数组上操作三、两道题的对比与总结表格题目核心问题递推公式优化方向不同路径路径计数dp[i][j] dp[i-1][j] dp[i][j-1]一维数组优化空间最小路径和路径和求最小值dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]原地修改数组这两道题是网格动态规划的入门模板它们的解题套路完全可以迁移到其他类似题目中状态定义通常定义dp[i][j]为到达(i,j)时的目标值路径数、路径和、最大值等。递推关系根据题目允许的移动方向只能右 / 下找到当前状态与上一状态的关系。边界初始化处理第一行和第一列因为它们只能从一个方向过来。空间优化利用滚动数组或原地修改将空间复杂度从二维降到一维甚至常数级。四、写在最后刷完这两道题你会发现动态规划的核心就是 **“大事化小小事化了”**把大问题拆解成一个个小的子问题找到它们之间的递推关系然后用空间换时间一步步算出最终结果。