原题链接

动态规划

定义状态

先明确题意，机器人只能选择向下或者向右走。

使用dp[i][j]来表示终点坐标(i, j)。

• 向下走:dp[i-1][j]
• 向右走:dp[i][j-1]

状态转移方程

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

处理边界

• i 和 j 分别等于 0 时，不满足要求需要被忽略。
• 初始条件 (0, 0) = 1，也就是终点与出发点重合。

constuniquePaths=(m,n)=>{constdp=Array.from(Array(n),()=>Array(m).fill(1))for(leti=1;i<n;i++){for(letj=1;j<m;j++){dp[i][j]=dp[i][j-1]+dp[i-1][j]}}returndp[n-1][m-1]}

• 时间复杂度: O(m * n)
• 空间复杂度: O(m * n)

降维

每次只需要从上边和左边的位置转移过来，所以我们可以用一个一维数组来优化空间，滚动更新每行的路径数量。

• dp[j]: 第 x 行第j列的路径数量

状态转移方程

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

第 i 行第 j 列位置的路径数量 = 第 i 行第 j - 1 列位置的路径数量 + 第 i - 1 行第 j 列位置的路径数量

constuniquePaths=function(m,n){constdp=newArray(n).fill(1)for(leti=1;i<m;i++){for(letj=1;j<n;j++){dp[j]=dp[j-1]+dp[j]}}returndp[n-1]}

• 时间复杂度：O(m * n)
• 空间复杂度: O(n)