华为OD机试C卷- 最小传输时延Ⅱ（Java & JS & Python）.md-私信看全套OD代码及解析

### 华为OD机试C卷 - 最小传输时延Ⅱ #### 题目背景与概述 本题目属于华为OD（Outsourcing Development）系列面试中的算法题，主要考察的是动态规划算法的应用能力。题目涉及到的数据结构是二维矩阵，并且通过模拟数据在网络中的传输过程来设置问题场景。该题的解决思路对于理解动态规划及其应用有着很好的指导意义。 #### 题目描述 在一个`M×N`的节点矩阵中，每个节点能够向八个方向（上、下、左、右及四个对角方向）传递数据包。在数据包传递过程中，每个节点会消耗一定的固定时延，但如果有连续的两个或以上的节点具有相同的时延，则可以减少相应数量的时延值。具体来说，如果有`K`个具有相同时延的连续节点传递数据，则可以减少`K-1`个时延值。目标是从左上角`(0,0)`开始传递数据包，直到传递至右下角`(M-1,N-1)`，并且找到整个传递过程中的最小总时延。 #### 输入描述 输入首先包含两个整数`M`和`N`，分别代表矩阵的行数和列数。接下来的`M`行中，每行包含`N`个整数，表示每个节点的时延值。 #### 输出描述 输出一个整数，表示从左上角到右下角的最小总时延。 #### 题目解析 这是一道典型的动态规划问题。我们可以通过定义一个三维数组`dp[m][n][k]`来表示到达`(m,n)`位置，且当前路径上连续相同时延节点的数量为`k`时的最短时延值。状态转移时，需要考虑从八个方向到达当前位置的情况，并根据路径上的连续相同延迟节点数量更新最小时延值。 #### 解题思路详解 1. **初始化**: 定义一个三维数组`dp`，其中`dp[m][n][k]`表示到达坐标`(m,n)`，且路径上连续相同延迟节点的数量为`k`时的最短时延。初始状态下，除了`dp[0][0][0]`被赋值为起点的延迟外，其他元素都被设置为无穷大。 2. **状态转移**: 对于每个位置`(i,j)`，遍历其八个相邻位置，计算从这些相邻位置转移到`(i,j)`时的最小时延。如果相邻位置`(x,y)`的延迟与当前位置相同，则可以减少一个延迟；如果不相同，则不减少。更新公式为： \[ dp[i][j][k] = \min(dp[i][j][k], dp[x][y][k'] + (matrix[i][j] != matrix[x][y] ? 1 : 0)) \] 其中`k'`为从相邻位置转移过来时连续相同延迟节点的数量，如果是首次出现新延迟，则`k'=0`；否则`k'`递减1。 3. **输出结果**: 最终的结果存储在`dp[M-1][N-1][0]`中，即到达右下角位置，且路径上连续相同延迟节点的数量为0时的最短时延。 #### Java实现示例 ```java import java.util.Scanner; public class MinDelay { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int M = scanner.nextInt(); int N = scanner.nextInt(); int[][] matrix = new int[M][N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { matrix[i][j] = scanner.nextInt(); } } System.out.println(minimumDelay(matrix, M, N)); } public static int minimumDelay(int[][] matrix, int M, int N) { int[][][] dp = new int[M][N][M + N]; for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { Arrays.fill(dp[i][j], Integer.MAX_VALUE); } } dp[0][0][0] = matrix[0][0]; for (int k = 0; k <= M + N - 2; k++) { for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (i > 0) updateDP(dp, matrix, i, j, k, i - 1, j); if (j > 0) updateDP(dp, matrix, i, j, k, i, j - 1); if (i < M - 1) updateDP(dp, matrix, i, j, k, i + 1, j); if (j < N - 1) updateDP(dp, matrix, i, j, k, i, j + 1); if (i > 0 && j > 0) updateDP(dp, matrix, i, j, k, i - 1, j - 1); if (i < M - 1 && j < N - 1) updateDP(dp, matrix, i, j, k, i + 1, j + 1); if (i > 0 && j < N - 1) updateDP(dp, matrix, i, j, k, i - 1, j + 1); if (i < M - 1 && j > 0) updateDP(dp, matrix, i, j, k, i + 1, j - 1); } } } return dp[M - 1][N - 1][0]; } private static void updateDP(int[][][] dp, int[][] matrix, int i, int j, int k, int x, int y) { int cost = dp[x][y][k == 0 ? 0 : k - 1] + (matrix[i][j] == matrix[x][y] ? 0 : 1); if (cost < dp[i][j][k]) { dp[i][j][k] = cost; } } } ``` #### Python实现示例 ```python def minimum_delay(matrix, M, N): dp = [[[float('inf')] * (M + N) for _ in range(N)] for _ in range(M)] dp[0][0][0] = matrix[0][0] for k in range(M + N - 1): for i in range(min(M, k + 1)): for j in range(min(N, k + 1)): if i > 0: update_dp(dp, matrix, i, j, k, i - 1, j) if j > 0: update_dp(dp, matrix, i, j, k, i, j - 1) if i < M - 1: update_dp(dp, matrix, i, j, k, i + 1, j) if j < N - 1: update_dp(dp, matrix, i, j, k, i, j + 1) if i > 0 and j > 0: update_dp(dp, matrix, i, j, k, i - 1, j - 1) if i < M - 1 and j < N - 1: update_dp(dp, matrix, i, j, k, i + 1, j + 1) if i > 0 and j < N - 1: update_dp(dp, matrix, i, j, k, i - 1, j + 1) if i < M - 1 and j > 0: update_dp(dp, matrix, i, j, k, i + 1, j - 1) return dp[M - 1][N - 1][0] def update_dp(dp, matrix, i, j, k, x, y): cost = dp[x][y][k == 0 and 0 or k - 1] + (matrix[i][j] == matrix[x][y] and 0 or 1) if cost < dp[i][j][k]: dp[i][j][k] = cost ``` 以上就是关于华为OD机试C卷- 最小传输时延Ⅱ题目的详细解析以及Java和Python的解题代码示例。通过上述分析和示例代码，希望能够帮助读者更好地理解和掌握动态规划算法的解题方法。