算法训练Day39|62.不同路径 ● 63. 不同路径 II

简介: 算法训练Day39|62.不同路径 ● 63. 不同路径 II

LeetCode:62.不同路径

62. 不同路径 - 力扣(LeetCode)


1.思路

想象成矩阵填格子,两个关键点,初始化和递推公式。

初始化除点(0,0)第一行第一列均为1,递推公式推导dp[i][j] = dp[i - 1][j] + dp[i][j - 1];


2.代码实现

 1class Solution {
 2    public int uniquePaths(int m, int n) {
 3        // 二维数组
 4        int[][] dp = new int[m][n];
 5
 6        // dp[m][n]:到达m,n位置,有dp[m][n]种路径
 7        // 初始化
 8        for (int i = 0; i < m; i++) {
 9            dp[i][0] = 1;
10        }
11        for (int i = 0; i < n; i++) {
12            dp[0][i] = 1;
13        }
14        for (int i = 1; i < m; i++) {
15            for (int j = 1; j < n; j++) {
16                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17            }
18        }
19        return dp[m - 1][n - 1];
20    }
21}
22

3.复杂度分析

时间复杂度:O(m * n).

空间复杂度:O(m * n).


LeetCode:63. 不同路径 II

63. 不同路径 II - 力扣(LeetCode)


1.思路

确定dp[][]数组,

条件排除,各种情况的考虑很关键,首尾节点和首行首列会影响初始化,当前节点影响dp[i][j]的值,


2.代码实现

 1class Solution {
 2    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3        // 求出总路径数 - 障碍位置路径数?
 4
 5        int m = obstacleGrid.length; // 获取行数
 6        int n = obstacleGrid[0].length; // 获取列数
 7        // dp[m][n] 表示节点(m,n)处潜在路径数
 8        int[][] dp = new int[m][n];
 9        // 当起始节点和终止节点均有障碍时,无结果,直接返回0
10        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
11            return 0;
12        }
13        // 每行的首位数字初始化(也即首列初始化),遇到障碍设置为0
14        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
15            dp[i][0] = 1;
16        }
17        // 每列的首位数字初始化(也即首行初始化),遇到障碍设置为0
18        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
19            dp[0][j] = 1;
20        }
21        // 遍历输出dp[][]数组值
22        for (int i = 1; i < m; i++) {
23            for (int j = 1; j < n; j++) [
24                if (obstacleGrid[i][j] == 0) { // 当前节点没有障碍时,正常执行
25                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
26                } else {
27                    dp[i][j] = 0; // 有障碍时直接赋值为0
28                }
29            ]
30        }
31        // 数组下标从0 开始,m - 1, n - 1也就代表(m,n)位置
32        return dp[m - 1][n - 1];
33
34    }
35}
36

3.复杂度分析

时间复杂度:O(m * n).

空间复杂度:O(m * n).

相关文章
|
1月前
|
算法 机器人 定位技术
【VRPTW】基于matlab秃鹰算法BES求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)(Matlab代码实现)
【VRPTW】基于matlab秃鹰算法BES求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)(Matlab代码实现)
|
7天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
7天前
|
算法 数据挖掘 区块链
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
|
11天前
|
存储 算法 数据可视化
基于禁忌搜索算法的TSP问题最优路径搜索matlab仿真
本程序基于禁忌搜索算法解决旅行商问题(TSP),旨在寻找访问多个城市的最短路径。使用 MATLAB 2022A 编写,包含城市坐标生成、路径优化及结果可视化功能。通过禁忌列表、禁忌长度与藐视准则等机制,提升搜索效率与解的质量,适用于物流配送、路径规划等场景。
|
20天前
|
机器学习/深度学习 负载均衡 算法
【卡车和无人机协同配送路径优化】遗传算法求解利用一辆卡车和两架无人机配合,将小包裹递送给随机分布的客户,以使所有站点都由卡车或无人机递送一次后返回起始位置(中转站)研究(Matlab代码实现)
【卡车和无人机协同配送路径优化】遗传算法求解利用一辆卡车和两架无人机配合,将小包裹递送给随机分布的客户,以使所有站点都由卡车或无人机递送一次后返回起始位置(中转站)研究(Matlab代码实现)
|
17天前
|
机器学习/深度学习 传感器 算法
基于matlab瞬态三角哈里斯鹰算法TTHHO多无人机协同集群避障路径规划(目标函数:最低成本:路径、高度、威胁、转角)(Matlab代码实现)
基于matlab瞬态三角哈里斯鹰算法TTHHO多无人机协同集群避障路径规划(目标函数:最低成本:路径、高度、威胁、转角)(Matlab代码实现)
|
29天前
|
机器学习/深度学习 算法 数据挖掘
【配送路径规划】基于螳螂虾算法MShOA求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)研究(Matlab代码实现)
【配送路径规划】基于螳螂虾算法MShOA求解带时间窗的骑手外卖配送路径规划问题(目标函数:最优路径成本 含服务客户数量 服务时间 载量 路径长度)研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 Java
Java实现林火蔓延路径算法
记录正在进行的森林防火项目中林火蔓延功能,本篇文章可以较好的实现森林防火蔓延,但还存在很多不足,如:很多参数只能使用默认值,所以蔓延范围仅供参考。(如果底层设备获取的数据充足,那当我没说)。注:因林火蔓延涉及因素太多,如静可燃物载量、矿质阻尼系数等存在估值,所以得出的结果仅供参考。
42 4
|
3月前
|
数据采集 并行计算 算法
基于蚁群算法求解带时间窗的车辆路径问题
基于蚁群算法求解带时间窗的车辆路径问题
77 0
|
4月前
|
监控 算法 JavaScript
基于 JavaScript 图算法的局域网网络访问控制模型构建及局域网禁止上网软件的技术实现路径研究
本文探讨局域网网络访问控制软件的技术框架,将其核心功能映射为图论模型,通过节点与边表示终端设备及访问关系。以JavaScript实现DFS算法,模拟访问权限判断,优化动态策略更新与多层级访问控制。结合流量监控数据,提升网络安全响应能力,为企业自主研发提供理论支持,推动智能化演进,助力数字化管理。
111 4

热门文章

最新文章