LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

前言

博主介绍：✌目前全网粉丝2W+，csdn博客专家、Java领域优质创作者，博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容：Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引：博客目录索引(持续更新)

视频平台：b站-Coder长路

---

LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

题目描述与分类

牛客：不同路径的数目(一)

leetcode：LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】

题目内容：一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

思考区

分类：动态规划/线性DP（二维）

约束条件：

1、机器人每次只能往右或者往下走。

2、机器人不能越界。

---

思路

思路1：动态规划

定义状态方程：

dp[i][j] = val  i表示行，j表示列，val表示方案数量
当i>1 && j>1  dp[i][j] = dp[i][j-1] + dp[i-1][j]
当i=0时，dp[i][j] = dp[i][j-1]
当j=0时，dp[i][j] = dp[i-1][j]

复杂度分析：

• 时间复杂度：O(n*m)
• 空间复杂度：O(n*m)

代码：

import java.util.*;public class Solution {/*** * @param m int整型 * @param n int整型 * @return int整型*/public int uniquePaths (int m, int n) {//定义dp数组int[][] dp= new int[m][n];for (int i = 0;i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0) {dp[i][j] = 1;continue;}if (j == 0) {dp[i][j] = 1;continue;}dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
}

class Solution {//线性dp//dp(i, j) = dp(i-1,j) + dp(i,j-1)public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < m; i ++) {for (int j = 0; j < n; j ++) {if (i == 0 || j == 0) dp[i][j] = 1;else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
}

---

思路2：递归实现

import java.util.*;public class Solution {/*** * @param m int整型 * @param n int整型 * @return int整型*/public int uniquePaths (int m, int n) {if (m == 1 || n == 1) {return 1; }return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);}
}

上面的时间复杂度是2ⁿ，如何优化呢？进行记忆化状态方程

class Solution {private int[][] dp;public int uniquePaths(int m, int n) {if (dp == null) {dp = new int[m + 1][n + 1];}if (m == 1 || n == 1) {return 1;}if (dp[m][n] == 0) {dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);}return dp[m][n];}
}

---

简洁写法补充：2024.1.30

class Solution {int[][] dp = new int[101][101];//线性dp//dp(i, j) = dp(i-1,j) + dp(i,j-1)public int uniquePaths(int m, int n) {if (m == 1 || n == 1) dp[m][n] = 1;if (dp[m][n] != 0) return dp[m][n];dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);return dp[m][n];}
}

此时无论是时间还是空间复杂度与思路1一致。

---

资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅：在下方专栏👇🏻

• 长路-文章目录汇总（算法、后端Java、前端、运维技术导航）：博主所有博客导航索引汇总
• 开源项目Studio-Vue—校园工作室管理系统(含前后台，SpringBoot+Vue)：博主个人独立项目，包含详细部署上线视频，已开源
• 学习与生活-专栏：可以了解博主的学习历程
• 算法专栏：算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻，🍅文末获取开发资源及更多资源博客获取🍅

---

整理者：长路 整理时间：2024.1.31