多维动态规划

不同路径

中等#62Java时间 O(mn)空间 O(mn)

题目要做什么

机器人从 m×n 网格左上角出发,每次只能向右或向下移动一格,求到右下角的不同路径数。

题目示例输入m = 3, n = 7
题目示例输出28

01 为什么这样做

到达某格的最后一步来自上方或左方,因此路径数等于两者之和。第一行、第一列只有一种走法。

始终成立的条件

处理 (r,c) 时,上方和左方状态已经求出。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int uniquePaths(int m, int n) {3        int[][] dp = new int[m][n];4        for (int r = 0; r < m; r++) {5            for (int c = 0; c < n; c++) {6                if (r == 0 || c == 0) dp[r][c] = 1;7                else dp[r][c] = dp[r - 1][c] + dp[r][c - 1];8            }9        }10        return dp[m - 1][n - 1];11    }12}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索