☆打卡算法☆LeetCode 62、不同路径 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

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]

这是从左上角开始，向下或者向右移动，然后推导而来。

那么遍历方程就是从左向右，向下遍历即可。