☆打卡算法☆LeetCode 64、最小路径和 算法解析

简介: “给定一个网格,找出一条从左上角到右下角的数字总和最大的路径。”

一、题目


1、算法题目

“给定一个网格,找出一条从左上角到右下角的数字总和最大的路径。”

题目链接:

来源:力扣(LeetCode)

链接:64. 最小路径和 - 力扣(LeetCode) (leetcode-cn.com)


2、题目描述

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明: 每次只能向下或者向右移动一步。

网络异常,图片无法展示
|

示例 1:
输入: grid = [[1,3,1],[1,5,1],[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
复制代码
示例 2:
输入: grid = [[1,2,3],[4,5,6]]
输出: 12
复制代码


二、解题


1、思路分析

这道题没跑了,还是用动态规划,但是由于本题是要找一条最大数字和的路径,因此路径是唯一的。

对于不在第一行第一列的元素,可以从上一个元素移动一步到达,元素对应的最小路径等于上一个元素对应的最小路径和中的最小值加上当前元素的值。


2、代码实现

代码参考:

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[,] dp = new int[m + 1, n + 1];
        for (int i = 2; i <= m; i++) dp[i, 0] = int.MaxValue;
        for (int j = 2; j <= n; j++) dp[0, j] = int.MaxValue;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m, n];
    }
}
复制代码

网络异常,图片无法展示
|


3、时间复杂度

时间复杂度 : O(mn)

其中m是网格的长,n是网格的宽,只需要遍历一遍网格即可求得答案。

空间复杂度: O(mn)

其中m是网格的长,n是网格的宽。


三、总结

空间复杂度可以优化到原地工作,也就是O1,但是会破坏原矩阵的数据。

通过分析可以发现,数据在扫描矩阵的时候,原数据信息只在扫描的时候用到一次,后续便不会再使用。

所以扫描写dp的时候,可以直接进行覆盖,而不会影响最终的结局。

也就是利用了系统为grid分配的内存进行记录动态规划的dp。



相关文章
|
19天前
|
机器学习/深度学习 算法 C++
【DFS/回溯算法】2016年蓝桥杯真题之路径之谜详解
题目要求根据城堡北墙和西墙箭靶上的箭数,推断骑士从西北角到东南角的唯一路径。每步移动时向正北和正西各射一箭,同一格不重复经过。通过DFS回溯模拟“拔箭”过程,验证路径合法性。已知箭数约束路径唯一,最终按编号输出行走顺序。
|
20天前
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
136 3
|
20天前
|
机器学习/深度学习 传感器 算法
【无人车路径跟踪】基于神经网络的数据驱动迭代学习控制(ILC)算法,用于具有未知模型和重复任务的非线性单输入单输出(SISO)离散时间系统的无人车的路径跟踪(Matlab代码实现)
【无人车路径跟踪】基于神经网络的数据驱动迭代学习控制(ILC)算法,用于具有未知模型和重复任务的非线性单输入单输出(SISO)离散时间系统的无人车的路径跟踪(Matlab代码实现)
|
22天前
|
机器学习/深度学习 人工智能 搜索推荐
从零构建短视频推荐系统:双塔算法架构解析与代码实现
短视频推荐看似“读心”,实则依赖双塔推荐系统:用户塔与物品塔分别将行为与内容编码为向量,通过相似度匹配实现精准推送。本文解析其架构原理、技术实现与工程挑战,揭秘抖音等平台如何用AI抓住你的注意力。
310 7
从零构建短视频推荐系统:双塔算法架构解析与代码实现
|
25天前
|
算法 数据可视化 异构计算
【车辆路径问题VRPTW】基于北极海鹦优化(APO)算法求解带时间窗的车辆路径问题VRPTW研究(Matlab代码实现)
【车辆路径问题VRPTW】基于北极海鹦优化(APO)算法求解带时间窗的车辆路径问题VRPTW研究(Matlab代码实现)
162 0
|
1月前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
118 8
|
1月前
|
算法 数据挖掘 区块链
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
基于遗传算法的多式联运车辆路径网络优优化研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 存储 算法
动态规划算法深度解析:0-1背包问题
0-1背包问题是经典的组合优化问题,目标是在给定物品重量和价值及背包容量限制下,选取物品使得总价值最大化且每个物品仅能被选一次。该问题通常采用动态规划方法解决,通过构建二维状态表dp[i][j]记录前i个物品在容量j时的最大价值,利用状态转移方程避免重复计算子问题,从而高效求解最优解。
273 1
|
1月前
|
算法 搜索推荐 Java
贪心算法:部分背包问题深度解析
该Java代码基于贪心算法求解分数背包问题,通过按单位价值降序排序,优先装入高价值物品,并支持部分装入。核心包括冒泡排序优化、分阶段装入策略及精度控制,体现贪心选择性质,适用于可分割资源的最优化场景。
178 1
贪心算法:部分背包问题深度解析
|
1月前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用

推荐镜像

更多
  • DNS