62. 不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
解题思路
动态规划分两个步骤:数学归纳法也是这个思路==微积分也是==就是遍历,不过是有一些记忆+分治+最优选择
1.找出边界
2.找出递推关系式
复杂度分析
- 时间复杂度:O(mn)。
空间复杂度:O(mn),即为存储所有状态需要的空间。注意到 f(i, j)f(i,j) 仅与第 ii 行和第i−1 行的状态有关,因此我们可以使用滚动数组代替代码中的二维数组,使空间复杂度降低为 O(n)。此外,由于我们交换行列的值并不会对答案产生影响,因此我们总可以通过交换 m 和 n 使得m≤n,这样空间复杂度降低至 O(min(m,n))。
//1,定义边界+ 函数关系式,时空都O(mn)
func uniquePaths(m int, n int) int {
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1) //初始化dp数组,DP[i][j]表示从点[1][1]走到[i][j]有多少种方法
}
for i := 0; i< m; i++ { //定义矩阵最左边的边界
dp[i][0] = 1
}
for j := 0; j< n; j++ { //定义矩阵最上边的边界
dp[0][j] = 1
}
for i := 1; i < m; i++ { //注意,此时不取等于号= !,因为返回的是n-1。 其实两个都做了初始化,可以取=
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1] //递推函数关系式
}
}
return dp[m-1][n-1] //走到右下角时,就是结果
}
//滚动数组 或者压缩为一维,优化空间On
func uniquePaths(m int, n int) int {
dp:=make([]int,n)
for j := 0; j<n; j++{
dp[j]=1 //1, 容易想到dp【j】,因为最后返回dp【n-1】
}
for i:=1; i < m; i++{ //2, 对i遍历,j进行记忆化 。严格来说这里m不能取=,n可以取=
for j:=1; j < n; j++{ //dp切片存储的是上一个次计算的值(外层for循环一次的值)
dp[j]=dp[j] + dp[j-1] //在计算当前次 的时候正好可以复用dp切片, 一直复用计算
}
}
return dp[n-1]
}