“给定m * n带下的网格, 从网格左上角出发,求有多少条到右下角的路径。”
题目链接:
来源:力扣(LeetCode)
链接:62. 不同路径 - 力扣(LeetCode) (leetcode-cn.com)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入: m = 3, n = 7
输出: 28
示例 2:
输入:m = 3, n = 2
输出:3
看到这种求出所有解的题,很容易就想到了动态规划。
这个首先要推算出来动态规划的方程,因为是从(0,0)触发,到(i,j)有dp[i][j]条路线。
求dp[i][j],要思考移动的方式:
因此得到动态规划方程:
dp[i,j] = dp[i-1,j]+dp[i,j-1]
因为dp[i,j]只有这两个方向可以过来,然后初始化数组,从dp[0,0]开始,参考代码如下。
代码参考:
public class Solution {
int[,] visited;
int[,] memo;
public int UniquePaths(int m, int n) {
visited = new int[m, n];
memo = new int[m, n];
return dfs(m, n, 0, 0);
}
public int dfs(int m, int n, int i, int j) {
if (i == m - 1 && j == n - 1) return 1;
int sum = 0;
// Let (i, j) be visited for current dfs recursion state
visited[i, j] = 1;
// Console.WriteLine(i + ", " + j);
if (i + 1 < m && j < n && visited[i + 1, j] != 1) {
sum += memo[i + 1, j] != 0 ? memo[i + 1, j] : dfs(m, n, i + 1, j);
}
if (i < m && j + 1 < n && visited[i, j + 1] != 1) {
sum += memo[i, j + 1] != 0 ? memo[i, j + 1] : dfs(m, n, i, j + 1);
}
// Set (i, j) back to un-visited for former dfs recursion state
visited[i, j] = 0;
return memo[i, j] = sum;
}
}
时间复杂度 : O(mn)
其中mn是矩阵的长宽,只需要遍历一遍矩阵即可求得答案。
空间复杂度: O(mn)
其中mn是矩阵的长宽。
这道题使用动态规划解题,重点是递归方程的推算。
回过头再看一下递归方程:
dp[i,j] = dp[i-1,j]+dp[i,j-1]
这是从左上角开始,向下或者向右移动,然后推导而来。
那么遍历方程就是从左向右,向下遍历即可。