62. Unique Paths 不同路径

题目

在一个 m*n 的网格上，有一个机器人。机器人一开始位于左上角，即 grid[0][0]。机器人要移动到右下角，机器人每次只能向下或向右移动。

给定两个整数 m 和 n 代表方格，返回机器人到达右下角可能的路径。

解析

从递归的角度来看，很简单，对于一个 m*n 的矩阵，机器人抵达右下角的可能数量为
func(m,n) = func(m-1,n) + func(m,n-1)
其中，当 m，n >=1
一旦 m == 1 或者 n == 1 了，则后续只有一种走发，直接返回

伪代码

if m == 1 || n == 1 
  return 1
return func()
if m > 1
  rst+=func(n)

代码

func uniquePaths(m int, n int) int {
    if m == 1 || n == 1 {
        return 1
    }
    return uniquePaths(m-1,n) + uniquePaths(m,n-1)
}

image.png

超时
以上是递归暴力解法。
其问题在于，m-1 和 n-1 同时缩小的过程中，会重复计算。为了避免重复，需要用空间换取时间的形式。
建立一个 m*n 方格，方格的没一个格子上存储的是到当前位置的路径数量。

1. dp[i][j] = dp[i-1][j] + dp[i][j-1]
2. dp[i][0] dp[0][j] 均为1

改进后代码

func uniquePaths(m int, n int) int {
    dp := make([]int, m*n)
    for i:=0;i<n;i++ {
        dp[0+i] = 1
    }
    for i:=0;i<m;i++ {
        dp[n*i+0] = 1
    }
    for i:=1;i<m;i++ {
        for j:=1;j<n;j++ {
            dp[i*n+j] = dp[(i-1)*n + j] + dp[i*n+j-1]
        }
    }
    return dp[m*n-1]
}

这种问题归属于，可以从前往后遍历，后一个问题的解依赖于前一个问题。

image.png