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

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

一、题目

1、算法题目

“给定m * n带下的网格，从网格左上角出发，求有多少条到右下角的路径。”

题目链接：

来源：力扣（LeetCode）

链接：62. 不同路径 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

代码语言：javascript复制

示例 1：
输入： m = 3, n = 7
输出： 28

代码语言：javascript复制

示例 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、代码实现

代码参考：

代码语言：javascript复制

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 &amp;&amp; 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 &amp;&amp; j < n &amp;&amp; visited[i   1, j] != 1) {
            sum  = memo[i   1, j] != 0 ? memo[i   1, j] : dfs(m, n, i   1, j);
        }
        if (i < m &amp;&amp; j   1 < n &amp;&amp; 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;
    }
}