LeetCode 62 不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
动态规划
确定动态规划数组的含义:定义二维动态规划数组
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][0]
也就是起点,那么只有一条路径,初始化为dp[0][0]=1
,对于dp[i][0]
也就是最左边一列的元素,只能从起点处不断向下走dp[i][0]=1
,同理最上方一行dp[0][i]=1
。遍历方式:采取逐行或者逐列遍历的方式都是可行的。
举例说明:
m = 3, n = 2
,首先完成初始化:dp[0][0]=0,dp[1][0]=1,dp[2][0]=1,dp[0][1]=1
再基础上逐行进行推导:第2行dp[1][1]=dp[0][1]+dp[1][0]=2
在此基础上推导第三行:dp[2][1]=dp[1][1]+dp[2][0]=3
验证正确。
1 | class Solution { |
对空间复杂度进行优化:使用一维的数组作为滚动数组来替代原本的动态规划数组。创建一个动态规划数组 dp[n]
全部初始化为1,也就是对应这原本动态规划数组的第一列,那么在次基础上即可按行进行计算:第二行的第一个值 dp[1][0]
,此处的第二维为0,值一定为1,不需要进行计算。第二行的第二值 dp[1][1]=dp[0][1]+dp[1][0]
转化到一维数组就是 dp[1]=dp[1]+dp[0]
计算第二行的第三个数值: dp[1][2]=dp[0][2]+dp[1][1]
此处的 dp[1][1]
已经计算出了,并且 dp[0][2]
就是 dp[2]
,那么就是 dp[2]=dp[2]+dp[1]
。
1 | class Solution { |
通过使用滚动数组的方式将空间复杂度削减到
组合数学求解
从出发点 [0,0]
走到终点 [m-1,n-1]
,至少需要向下走 m-1
步,向右走 n-1
步,总结需要 m+n-2
步,那么求解总共有多少中走法,就将问题转化为了:在 m+n-2
步中选取 m-1
步作为向下走的步数,剩余的 n-1
步自然就作为向右走的步数,那么对应路径数就为:
那么要实现
1 | class Solution { |
关于计算过程中的整除问题:
第一次(53 / 1)任何数都可整除1
第二次(53*52 / 1*2)连续的2个数中一定有一个是2的倍数
第三次(53*52*51 / 1*2*3)连续的3个数中一定有一个是3的倍数
以此类推,每次都可以整除