一、题目
1、算法题目
“给定m * n带下的网格， 从网格左上角出发，求有多少条到右下角的路径。”
题目链接：
来源：力扣（LeetCode）
链接：62. 不同路径 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
网络异常，图片无法展示
|
示例 1： 输入： m = 3, n = 7 输出： 28 复制代码
示例 2： 输入：m = 3, n = 2 输出：3 复制代码
二、解题
1、思路分析
看到这种求出所有解的题，很容易就想到了动态规划。
这个首先要推算出来动态规划的方程，因为是从(0,0)触发，到(i,j)有dp[i][j]条路线。
求dp[i][j]，要思考移动的方式：
- 如果向下走，那么就是从dp[i-1,j]走过来
- 如果向右走，那么就会从dp[i,j-1]走过来
因此得到动态规划方程：
dp[i,j] = dp[i-1,j]+dp[i,j-1]
因为dp[i,j]只有这两个方向可以过来，然后初始化数组，从dp[0,0]开始，参考代码如下。
2、代码实现
代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(mn)
其中mn是矩阵的长宽，只需要遍历一遍矩阵即可求得答案。
空间复杂度： O(mn)
其中mn是矩阵的长宽。
三、总结
这道题使用动态规划解题，重点是递归方程的推算。
回过头再看一下递归方程：
dp[i,j] = dp[i-1,j]+dp[i,j-1]
这是从左上角开始，向下或者向右移动，然后推导而来。
那么遍历方程就是从左向右，向下遍历即可。
