题目解析：机器人的路径难题
让我们先明确问题边界：一个机器人位于m x n网格的左上角（Start），每次只能向下或者向右移动一步，试图到达右下角（Finish）。问总共有多少条不同的路径？
举个直观的例子，当m=3, n=2时，机器人有3条路径可选：
向右 → 向下 → 向下
向下 → 向下 → 向右
向下 → 向右 → 向下
这个简单案例揭示了问题的本质：到达每个格子的路径数等于到达其上方格子与左方格子的路径数之和。这正是动态规划的典型特征——重叠子问题与最优子结构。
动态规划四步法：从思路到代码
第一步：定义状态
我们定义dp[i][j]表示到达第i行第j列的路径数量。这个二维数组将存储所有子问题的解，避免重复计算。
第二步：推导状态转移方程
由于机器人只能向下或向右移动，到达(i,j)的路径只能来自两个方向：
从上方(i-1,j)向下移动
从左方(i,j-1)向右移动
因此状态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]
第三步：初始化边界条件
网格的第一行和第一列需要特殊处理：
第一行所有格子dp[0][j] = 1（只能从左侧一直向右移动）
第一列所有格子dp[i][0] = 1（只能从上方一直向下移动）
第四步：确定计算顺序
按照从左到右、从上到下的顺序填充dp数组，确保计算dp[i][j]时，dp[i-1][j]和dp[i][j-1]已经计算完成。
代码实现：从二维到一维的优化
基础二维数组实现
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];// 初始化第一列for(int i = 0; i < m; i++) {dp[i][0] = 1;}// 初始化第一行for(int j = 0; j < n; j++) {dp[0][j] = 1;}// 填充dp数组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[j]和当前行的dp[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++) {for(int j = 1; j < n; j++) {dp[j] += dp[j-1];}}return dp[n-1];}}
复杂度分析
时间复杂度：O(m×n)，需要填充整个dp数组
空间复杂度：O(n)，优化后只需一维数组存储状态
同类拓展：63.不同路径II（含障碍物）
当网格中出现障碍物时（用1表示），我们需要在状态转移时增加判断：
如果当前格子是障碍物，则dp[i][j] = 0
初始化时遇到障碍物，后续格子均无法到达
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[] dp = new int[n];// 初始化第一行for(int j = 0; j < n; j++) {if(obstacleGrid[0][j] == 1) break;dp[j] = 1;}// 逐行更新for(int i = 1; i < m; i++) {// 处理每行第一个元素if(obstacleGrid[i][0] == 1) {dp[0] = 0;}for(int j = 1; j < n; j++) {if(obstacleGrid[i][j] == 1) {dp[j] = 0;} else {dp[j] += dp[j-1];}}}return dp[n-1];}}
动态规划思想的迁移应用
不同路径问题揭示了动态规划的本质：将复杂问题分解为重叠子问题，通过存储中间结果避免重复计算。这种思想可以迁移到许多类似问题：
64.最小路径和：将路径数量改为路径权重，状态转移方程变为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
931.下降路径最小和：允许从正上方、左上方或右上方到达，状态转移扩展为三个方向
LCR 166.珠宝的最高价值：网格每个格子有价值，求最大价值路径
总结：动态规划的黄金法则
解决动态规划问题的核心在于：
找到状态定义，准确定义子问题
推导状态转移方程，描述子问题间的关系
确定边界条件，初始化基础情况
优化空间复杂度，去除冗余存储
不同路径问题作为动态规划的入门经典，其解题思路可以迁移到各类网格路径、序列规划问题中。掌握这种"自底向上"的解题思维，将为解决更复杂的算法问题奠定基础。
最后思考一个问题：如果网格规模扩大到1000x1000，一维数组的空间优化还够用吗？欢迎在评论区分享你的想法！