牛客热题:矩阵的最小路径和

📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

牛客热题:矩阵的最小路径和

题目链接

矩阵的最小路径和_牛客题霸_牛客网 (nowcoder.com)

方法一:二维dp

思路

①状态表示:

d p [ i ] [ j ] dp[i][j] dp[i][j] 表示为从起点(0, 0)到(i, j)位置的最小路径和

②初始化:

​ 首先对于第一行第一列来说,他们的路径都只有一条,就是从他们的上方或者左方到达,因此我们可以直接计算出他们的路径和。

③状态转移方程:

​ 对于每一个位置来说,有两个路径来源,我们选取路径和小的就可以。

d p [ i ] [ j ] = m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) + m a t r i x [ i ] [ j ] dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j] dp[i][j]=min(dp[i1][j],dp[i][j1])+matrix[i][j]

④填表顺序:

​ 我们发现当前位置状态的获取都需要依赖上方和左方位置的状态,因此我们填表顺序为:

从上到下,从左到右。

⑤返回结果:

​ 因为答案要求的是从起点到终点的最小路径和,因此我们要返回的结果就是 d p [ m − 1 ] [ n − 1 ] dp[m - 1][n - 1] dp[m1][n1]

代码

int minPathSum(vector<vector<int> >& matrix) 
    {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        //初始化
        dp[0][0] = matrix[0][0];
        for(int i = 1; i < m || i < n; ++i)
        {
            if(i < m) dp[i][0] = dp[i - 1][0] + matrix[i][0];
            if(i < n) dp[0][i] = dp[0][i - 1] + matrix[0][i];
        }

        for(int i = 1; i < m; ++i)
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        return dp[m - 1][n - 1];
    }

复杂度

时间复杂度:遍历了一次二维dp数组: O ( m ∗ n ) O(m * n) O(mn)

空间复杂度:使用了额外的二维数组: O ( m ∗ n ) O(m * n) O(mn)

相关推荐

  1. 【打卡】网:BM68 矩阵路径

    2024-06-10 14:34:04       31 阅读
  2. 【打卡】网:BM61 矩阵长递增路径

    2024-06-10 14:34:04       27 阅读

最近更新

  1. postman接口测试工具详解

    2024-06-10 14:34:04       0 阅读
  2. C语言运算类型有哪些

    2024-06-10 14:34:04       0 阅读
  3. 【Redis】为什么是单线程?为什么这么快呢?

    2024-06-10 14:34:04       0 阅读
  4. 小程序的生命周期以及页面生命周期

    2024-06-10 14:34:04       0 阅读
  5. mysql容器问题mbind: Operation not permitted

    2024-06-10 14:34:04       0 阅读
  6. NFS网络文件存储入门

    2024-06-10 14:34:04       0 阅读
  7. 小甲鱼——字典

    2024-06-10 14:34:04       0 阅读
  8. Scrapy与MongoDB的异步数据存储

    2024-06-10 14:34:04       0 阅读
  9. k8s及etcd的每日自动备份及故障时的还原脚本

    2024-06-10 14:34:04       0 阅读

热门阅读

  1. Vue3学习

    2024-06-10 14:34:04       3 阅读
  2. 使用c语言实字符串倒置及逆波兰数(栈)

    2024-06-10 14:34:04       3 阅读
  3. web前端报名点:深入探索与报名流程指南

    2024-06-10 14:34:04       4 阅读
  4. 深拷贝&浅拷贝解析,从原理理解深拷贝

    2024-06-10 14:34:04       4 阅读
  5. 不要使用业务键作为数据库主键

    2024-06-10 14:34:04       5 阅读
  6. 爬山算法的详细介绍

    2024-06-10 14:34:04       3 阅读
  7. SSRF 漏洞实践:端口扫描与任意文件读取

    2024-06-10 14:34:04       3 阅读
  8. SpringBoot实现上传头像(查看头像)

    2024-06-10 14:34:04       4 阅读
  9. 模拟CAS算法案例

    2024-06-10 14:34:04       3 阅读
  10. DeepSpeed Autotuning

    2024-06-10 14:34:04       2 阅读
  11. 10-Eureka-服务注册

    2024-06-10 14:34:04       3 阅读