当前位置：首页 > news >正文

连云港人才专业化网站安卓客户端开发

news 2025/9/17 2:28:55

连云港人才专业化网站,安卓客户端开发,公司主营网站开发怎么做账,鞍山网民文章目录前言LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】题目描述与分类思路思路1：动态规划思路2：递归实现简洁写法补充：2024.1.30 资料获取前言博主介绍：✌目前全网粉丝2W，csdn博客专家、…

文章目录

前言
LeetCode、62.不同路径的数目(一)【简单，动态规划或递归】
- 题目描述与分类
- 思路
- - 思路1：动态规划
  - 思路2：递归实现
  - 简洁写法补充：2024.1.30
资料获取

前言

博主介绍：✌目前全网粉丝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];}
}