LeetCode 题解:62. 不同路径,动态规划,JavaScript,详细注释
![LeetCode题解:62. 不同路径,动态规划,JavaScript,详细注释](https://static001.geekbang.org/infoq/39/39e4af1fec823a1382b4e24773dbe103.png)
原题链接:https://leetcode-cn.com/problems/unique-paths/
解题思路:
在网格中的任意一点,都有向右和向下两种走法。同时它也是从上方和左方两个位置走过来的。
那么,任意一点的走法数量,等于从起点走到上方和左方点的数量之和。
第一行和第一列都只有一种走法,就是从起点一直走到底。
我们可以用一个二维数组,画出网格中每个点的走法数量,一直递推到终点,终点存储的就是所有的走法数量。
因此动态规划的状态转移方程为:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
。
复制代码
实际上我们计算某个点的步数时,只需要左边和上边的值即可。
我们可以只用一个数组,而且我们每次都是从左向右生成步数,因此就有以下特点:
* 因此对于第 m 行来说,它存储的就是 m-1 行的步数。
* 对于第 n 列来说,它的 n-1 位置存储了 n-1 位置的步数。
代码优化如下:
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/a98b8c7b1628ade205d57d0d0】。文章转载请联系作者。
评论