1.1. 题目

1.1.1. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

1.1.2. 题解:

• m x n 的格子,如果是个数组(切片),那么m就是x轴,n就是y轴, 申明的时候应该是 [n][m]int,可千万别搞错了
• 起点是左上角,也就是坐标 0,0的地方!终点是右下角坐标是 m,n的地方!
• 只能往右和往下移动,不能左转,也不能斜着对角走

1.1.3. 思路:

• 写了几次动归,知道这题肯定是动归解决了!
• 从终点看,到m,n的路径要么从 m-1,n(假设为A点),要么从 m,n-1(假设为B点)这两个地方来(暂时不考虑就一层的情况)
  • 那么到终点可能的路径就是 起点到A点的路径 + 起点到B点的路径
  • 那么A点路径的个数是多少呢,是它左边的路径 + 它上面的路径
  • ...
  • 一直拆分到 原点
• 思路出来了,代码该如何呢,已知原点的路径是 1,原点右边只可能是原点来,所以原点右边也是1,同理原理下面的格子也都是1,即边界条件,如果x轴为零或者y轴为零,那么这两条轴上的格子路径都是1
• 非x,y轴上的点,都是它上面和左边的路径之和!
• 代码就很简单了,定义一个二维切片保存每个格子的路径可能性条数
• 循环每个格子,返回最后一个格子的!

1.1.4. 代码:

func uniquePaths(m int, n int) int {

    if n == 0 || m == 0{
        return 1
    }

    dp := make([][]int,n)

    for i:=0;i<n;i++ {
        dps := make([]int,m)
        for j:=0;j<m;j++ {
            if i == 0 || j == 0 {
                dps[j] = 1
            } else {
                dps[j] = dp[i-1][j] + dp[i][j-1]
            }
            dp[i] = dps
        }

    }

    return dp[n-1][m-1]
}

代码