动态规划——路径问题:931.下降路径最小和

server/2024/11/25 6:29:31/

文章目录

  • 题目描述
  • 算法原理
    • 1.状态表示(经验+题目)
    • 2.状态转移方程
    • 3.初始化
    • 4.填表顺序
    • 5.返回值
  • 代码实现
    • C++
    • Java

题目描述

题目链接:931.下降路径最小和
在这里插入图片描述
关于这⼀类题,看过我之前的博客的朋友对于状态表示以及状态转移是⽐较容易分析出来的。比较难的地方可能就是对于边界条件的处理。

算法原理

1.状态表示(经验+题目)

对于这种路径类的问题,我们的状态表示⼀般有两种形式:

  • 从 [i, j] 位置出发,到达⽬标位置有多少种方式;
  • 从起始位置出发,到达 [i, j] 位置,⼀共有多少种方式。

这⾥选择第⼆种定义状态表示的方式:
dp[i][j] 表示:到达 [i, j] 位置时,所有下降路径中的最小和。

2.状态转移方程

在这里插入图片描述

根据最近的一步划分问题。对于普遍位置 [i, j] ,根据题意得,到达 [i, j] 位置可能有三种情况:

  • 从正上方 [i - 1, j] 位置转移到 [i, j] 位置;
  • 从左上方 [i - 1, j - 1] 位置转移到 [i, j] 位置;
  • 从右上方 [i - 1, j + 1] 位置转移到 [i, j] 位置;

我们要的是三种情况下的最小值,然后再加上矩阵在 [i, j] 位置的值。
所以得出状态转移方程:

dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 
1])) + matrix[i - 1][j - 1]

3.初始化

在这里插入图片描述

可以在最前面加上⼀个辅助结点,帮助我们初始化。使用这种技巧要注意两个点:

  • 辅助结点里面的值要保证后续填表是正确的
  • 下标的映射关系

在本题中,需要加上一行,并且加上两列。所有的位置都初始化为INT_MAX,然后将第⼀行初始化为 0 即可。

4.填表顺序

根据状态表示,填表的顺序是从上往下即可,同一行的顺序可以随意。

5.返回值

注意这⾥不是返回 dp[m][n] 的值!题⽬要求只要到达最后一行就行了,因此这⾥应该返回 dp 表中最后一行的最小值

代码实现

C++

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {//1.创建一个dp表int n = matrix.size();vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));//2.初始化for(int k = 0;k <= n + 1;++k)dp[0][k] = 0;//3.填表for(int i = 1;i <= n;++i)for(int j = 1;j <= n;++j)dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];//这边要注意一下下标的映射关系//4.返回值int ret = INT_MAX;for(int m = 1;m <= n;++m)ret = min(ret, dp[n][m]);return ret;}
};

Java

java">class Solution {public int minFallingPathSum(int[][] matrix) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回结果int n = matrix.length;int[][] dp = new int[n + 1][n + 2];for (int i = 1; i <= n; i++)dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1],dp[i - 1][j + 1])) + matrix[i - 1][j - 1];int ret = Integer.MAX_VALUE;for (int j = 1; j <= n; j++)ret = Math.min(ret, dp[n][j]);return ret;}
}

http://www.ppmy.cn/server/38352.html

相关文章

ICode国际青少年编程竞赛- Python-1级训练场-变量的计算

ICode国际青少年编程竞赛- Python-1级训练场-变量的计算 1、 a 2 for i in range(4):Spaceship.step(a-1)Dev.step(a)Dev.step(-a)a a 12、 a 2 for i in range(4):Dev.step(2 a)Dev.step(-a)Dev.turnRight()a a 13、 y 4 for i in range(3):Dev.step(y)Dev.turnRigh…

java基于云计算的SaaS医院his信息系统源码 HIS云平台源码

目录 云HIS功能模块 1、预约挂号&#xff1a; 2、药库管理&#xff1a; 3、门诊医生站&#xff1a; 4、门诊费用&#xff1a; 5、药房管理&#xff1a; 6、治疗室&#xff08;门诊护士工作站&#xff09;&#xff1a; 7、统计分析&#xff1a; 8、财务管理&#xff1a;…

2万字长文:海豚调度器(DolphinScheduler)面试题深入了解

目录 海豚调度器的主要功能和特点 海豚调度器与Oozie、Azkaban等调度器相比的优势

百倍潜力股Aleo即将上线,布局正当时!牛市来时,你得有币!

前言 在加密货币市场&#xff0c;2024年被众多市场专家预测为迎来新一轮牛市的关键年份。这一预测背后&#xff0c;潜藏着多种可能推动牛市的因素。其中&#xff0c;下一次比特币&#xff08;BTC&#xff09;的减半事件&#xff0c;以及2024年 BTC 现货ETF的推出&#xff0c;都…

Linux网络编程:TCP编程实现

目录 1、前言 2、函数介绍 2.1 socket函数 与 通信域 2.2 bind函数 与 通信结构体 2.2.1 domain通信地址族 与 通信结构体 2.2.2 IPv4地址族结构体 2.2.3 通用地址族结构体 2.2.4 示例&#xff1a;为套接字fd绑定通信结构体addr 2.3 listen函数 与 accept函数 …

企业车辆管理系统参考论文(论文 + 源码)

【免费】关于企业车辆管理系统.zip资源-CSDN文库https://download.csdn.net/download/JW_559/89282550 企业车辆管理系统 摘 要 随着经济的日益增长,车辆作为最重要的交通工具,在企事业单位中得以普及,单位的车辆数目已经远远不止简单的几辆,与此同时就产生了车辆资源的合理…

【MATLAB源码-第205期】基于matlab的LDPC译码算法仿真,对比BF算法,最小和算法,对数BP和概率BP四种算法。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 LDPC 码简介 LDPC码是一种通过稀疏奇偶校验矩阵定义的线性分组码&#xff0c;1962年由Gallager首次提出。这种码具有高效的解码性能&#xff0c;尤其在接近香农极限的情况下&#xff0c;其性能表现尤为突出。LDPC码的核心特…

word格式技巧

文章目录 论文格式技巧论文交叉引用怎么弄论文的页码怎么弄 论文格式技巧 论文交叉引用怎么弄 1.取消文献原有的编号 2.定义新编号 3.具体编号设置 4.在引用的地方插入&#xff0c;具体引用选项卡–>交叉引用–>选择后插入 2. 4. 论文的页码怎么弄 假设我们有这样一…