62_unique_paths

62. 不同路径 中等

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

输入：m = 3, n = 3
输出：6

提示：

- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 109

代码参考：

```go
package main

import "fmt"

func main() {
    fmt.Println(uniquePaths(7, 3)) // 7列 3行
}

// 感觉是个数学问题
func uniquePaths(m int, n int) int {
    paths := make([][]int, n)
    for i := range paths {
        paths[i] = make([]int, m)
    }

    for r := n - 1; r >= 0; r-- {
        paths[r][m-1] = 1
    }
    for c := m - 1; c >= 0; c-- {
        paths[n-1][c] = 1
    }

    for r := n - 1 - 1; r >= 0; r-- { // 从倒数第二行向前
        for c := m - 1 - 1; c >= 0; c-- { // 每行从后向前走
            paths[r][c] = paths[r][c+1] + paths[r+1][c]
        }
    }

    // fmt.Println(paths)
    // [28 21 15 10 6 3 1]
    // [7   6  5  4 3 2 1]
    // [1   1  1  1 1 1 1]
    return paths[0][0]
}