跳转至

LC62 - 不同路径

UniquePaths.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package DP2

func uniquePaths(m int, n int) int {
    return uniquePaths1(m, n)
}

// 时间复杂度: O(m), 空间复杂度: O(1)
func uniquePaths1(m int, n int) int {
    M := m + n - 2
    N := min(m-1, n-1)
    ans := 1
    for i, j := 1, M; i <= N; i, j = i+1, j-1 {
        ans = ans * j / i
    }
    return ans
}

// 时间复杂度: O(m * n), 空间复杂度: O(m * n)
func uniquePaths2(m int, n int) int {
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if i == m-1 && j == n-1 {
                dp[i][j] = 1
            } else {
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
            }
        }
    }
    return dp[0][0]
}