不同路径

1. 题目描述

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

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

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

2. 思路

1. 思路一
   • DFS：当走到(m-1, n-1)时就是到达终点
   • 只能往右或者往下走，因此不会走重复(i,j)，故不需要set记录走过的(i,j)
2. 思路二
   • DFS+缓存
3. 思路三
   • 动态规划

3. 实现

3.1. DFS

func uniquePaths(m int, n int) int {
    count := 0

    uniquePathsDFS(0, 0, m, n, &count)

    return count
}

func uniquePathsDFS(row, col, m, n int, count *int) {
    if invalid(row, col, m, n) {
        return
    }

    if exceedEnd(row, col, m, n) {
        *count++
        return
    }

    uniquePathsDFS(row+1, col, m, n, count)
    uniquePathsDFS(row, col+1, m, n, count)
}

func invalid(row, col, m, n int) bool {
    
    if row < 0 || row >= m || col < 0 || col >= n {
        return true
    }

    return false
}

func exceedEnd(row, col, m, n int) bool {
    if row==m-1 && col == n-1 {
        return true
    }

    return false
}

3.2. DFS+缓存

func uniquePaths(m int, n int) int {
    memo := make(map[string]int, 0)
    return uniquePathsDFS(0, 0, m, n, memo)
}

func uniquePathsDFS(row, col, m, n int, memo map[string]int) int {
    count, ok := memo[getKey(row, col)]
    if ok {
        return count
    }

    if invalid(row, col, m, n) {
        return 0
    }

    if exceedEnd(row, col, m, n) {
        return 1
    }

    leftCount := uniquePathsDFS(row+1, col, m, n, memo)
    rightCount := uniquePathsDFS(row, col+1, m, n, memo)

    count = leftCount + rightCount
    memo[getKey(row, col)] = count
    return count
}

func invalid(row, col, m, n int) bool {
    
    if row < 0 || row >= m || col < 0 || col >= n {
        return true
    }

    return false
}

func exceedEnd(row, col, m, n int) bool {
    if row==m-1 && col == n-1 {
        return true
    }

    return false
}

func getKey(row, col int) string {
    return fmt.Sprintf("%v:%v", row, col)
}

3.3. 动态规划

func uniquePaths2(m int, n int) int {
	dp := make([][]int, m, m)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n, n)
	}

	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}

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

4. 参考

• 62. 不同路径 - 力扣（LeetCode）