leetcode不同路径

这道题是经典的动态规划问题。我们可以定义一个二维数组 $dp$，其中 $dp[i][j]$ 表示到达 $(i,j)$ 位置时的不同路径数目。则有状态转移方程：

$$
dp[i][j] = dp[i-1][j] + dp[i][j-1]
$$

边界条件为 $dp[0][0] = 1$，$dp[i][0] = 1$，$dp[0][j] = 1$。

最终结果即为 $dp[m-1][n-1]$，其中 $m$ 和 $n$ 分别为行数和列数。

下面是具体的代码实现：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

相关问题

如何修改vscode leetcode 默认路径

在Visual Studio Code (VSCode) 中配置 LeetCode 的默认路径，主要是为了指定代码片段存储的位置，以便于管理和访问LeetCode题目相关的代码模板。以下是步骤：

1. 打开 VSCode，点击左上角的 "文件" 菜单，然后选择 "首选项" > "设置"。

2. 进入设置页面，如果你还没有开启用户代码片段支持，可以在搜索框输入 `vetur.codeSnippetsPath` 或者直接键入 `"vetur.codeSnippetsPath": "path/to/your/leetcode/snippets"`，这里的 "path/to/your/leetcode/snippets" 需替换为你想要存放代码片段的具体文件夹路径。

3. 如果已经开启了用户代码片段支持，那么你只需要在 `"vetur.codeSnippets"` 对象下添加 LeetCode 相关的路径，例如：

   "vetur.codeSnippets": {
       "leetcode": "path/to/your/leetcode/snippets"
   }

4. 确认路径无误后，保存设置即可。此后，当你在 LeetCode 插件中创建或编辑代码片段时，它们会保存到指定的文件夹内。

Leetcode:63题不同路径||

根据给出的参考代码，Leetcode第63题的题目是不同路径II。这道题目给定了一个包含障碍物的网格，机器人只能向右或向下移动，需要计算从左上角到右下角的不同路径数。如果有障碍物，那么该位置将被视为不可通过。

该问题可以使用动态规划来解决。我们可以创建一个与给定网格相同大小的二维数组dp，其中dp[i][j]表示从起点到网格中(i,j)位置的不同路径数。然后，我们可以根据以下状态转移方程来计算不同路径数：

- 如果网格中(i,j)位置有障碍物，则dp[i][j]为0，因为此位置无法通过。
- 否则，dp[i][j]等于dp[i-1][j]加上dp[i][j-1]，因为机器人只能向右或向下移动。

最后，dp[m-1][n-1]即为从起点到终点的不同路径数。

代码示例：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m][n];
        
        // 初始化第一行和第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                break;
            }
            dp[0][j] = 1;
        }
        
        // 计算不同路径数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        return dp[m-1][n-1];
    }
}