代码随想录算法训练营第三十三天 | 62、63

算法
, , ,

62. 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

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

63. 不同路径 II

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
35
36
37
38
package main

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    if obstacleGrid[0][0] == 1 {
        return 0
    }

    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    dp := make([]int, n)

    // 初始化第一行
    dp[0] = 1
    for j := 1; j < n; j++ {
        if obstacleGrid[0][j] == 1 {
            dp[j] = 0
        } else {
            dp[j] = dp[j-1]
        }
    }

    // 处理后续行
    for i := 1; i < m; i++ {
        // 处理第一列
        if obstacleGrid[i][0] == 1 {
            dp[0] = 0
        }
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                dp[j] = 0
            } else {
                dp[j] = dp[j] + dp[j-1]
            }
        }
    }
    return dp[n-1]
}