目录
求路径
访问量:306

一、简介

一个机器人在m×n大小的地图的左上角(起点)。

机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。

可以有多少种不同的路径从起点走到终点?

二、实现

/**
  * 
  * @param m int整型 
  * @param n int整型 
  * @return int整型
  dp[i][j] 代表从dp[0][0]到 第i+1行,第j+1列需要路径数
*/
func uniquePaths( m int ,  n int ) int {
    // write code here
    dp := make(map[int]map[int]int)
    for i:=0; i< m ; i++ {
        if _,isOk := dp[i]; !isOk {
            dp[i] = make(map[int]int)
        }
        
        for j:=0; j < n ; j++ {
            if i==0 || j == 0 {
                 dp[i][j] = 1
            } else {
                dp[i][j]  = dp[i-1][j] + dp[i][j-1]
            }
        }
    }
   
   return dp[m -1][n -1]
}