获取题库不需要订阅专栏,可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
有M*N的节点矩阵,每个节点可以向8个方向(上、下、左、右及四个斜线方向)转发数据包,每个节点转发时会消耗固定时延,连续两个相同时延可以减少一个时延值(即当有K个相同时延的节点连续转发时可以减少K- 1个时延值),
求左上角(0,0)开始转发数据包到右下角(M-1,N- 1)并转发出的最短时延。
输入描述
第一行两个数字,M、N,接下来有M行,每行有N个数据,表示M* N的矩阵。
输出描述
最短时延值。
题目解析
这是一个典型的动态规划问题,其中状态转移需要考虑路径上的连续相同延迟可以减少总延迟的特性。我们可以定义一个三维数组 dp[m][n][k] 来存储到达 (m, n) 位置,且当前路径上连续相同延迟节点数为 k 的最短延迟。状态转移时,我们需要考虑从8个方向到达当前位置的情况,并且更新最小延迟值。
Java算法源码
import java.util