Leetcode 62: 不同路径
Leetcode 62: 不同路径
问题描述：
一个机器人位于一个 (m \times n) 网格的左上角（起始点位于 ((0, 0))）。
机器人每次只能向下或向右移动一步。网格的右下角为终点（位于 ((m-1, n-1))）。
计算机器人从左上角到右下角的不同路径总数。
适合面试的解法：动态规划（DP）
动态规划（DP）是一种经典的方法，非常适合解决路径问题。通过定义状态和状态转移方程，我们可以高效地求解从起点到终点的路径数。
解题思路
核心步骤：动态规划
1. 状态定义
- 定义
dp[i][j]表示从起点 ((0, 0)) 到达位置 ((i, j)) 的不同路径数。
2. 状态转移方程
- 机器人从当前位置 ((i, j)) 可以通过以下两种方式到达：