62. Unique Paths

一个m*n的矩阵，一个机器人从左上到右下角移动，每次只能往右或往下移动一步，一共有多少种独立的路径

思路：动态规划，状态转移方程： dp[x][y] = dp[x - 1][y] + dp[x][y - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 6 star,
        # 动态规划，状态转移方程： dp[x][y] = dp[x - 1][y] + dp[x][y - 1]
        dp = [[1 for _ in range(n)] for _ in range(m)]
        for i in range(1, n):
            for j in range(1, m):
                dp[j][i] = dp[j][i-1] + dp[j-1][i]
        return dp[-1][-1]

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 6 star, 动态规划，状态转移方程dp[i[[j] = dp[i-1][j] + dp[i][j-1],
//首先需要把dp的第一行和第一列全部置为1
func uniquePaths(m int, n int) int {
	dp := make([][]int, m)
	for i:=0; i<m; i++ {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j:=0; j<n; j++ {
		dp[0][j] = 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]

}