首页 > 试题广场 >

小强的神奇矩阵

[编程题]小强的神奇矩阵

热度指数：1648 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小强有一个 $3\times n$ 的矩阵 $\mathit a$ ，他将 $\mathit a$ 中每列的三个数字中取出一个按顺序组成一个长度为 $\mathit n$ 的数组 $\mathit b$ ，即 $b_i$ 可以是 $a_{1,i},a_{2,i},a_{3,i}$ 其中任意一个。问 $\sum_{i=1}^{n-1}\left|b_i-b_{i+1}\right|$ 的最小值是多少。

输入描述:

第一行，一个正整数。
第二行到第四行输入一个的矩阵，每行输入个正整数。
。

输出描述:

一行一个正整数表示答案。

示例1

输入

输出

说明

数组可以为，答案为。

算法知识视频讲解

Python

O_n2

动态规划

def compute(matrix, n):
    dp_matrix = [[0, 0, 0]]
    for j in range(1, n):
        delta_i = []
        for i in range(3):
            d0 = abs(matrix[i][j] - matrix[0][j-1]) + dp_matrix[-1][0]
            d1 = abs(matrix[i][j] - matrix[1][j-1]) + dp_matrix[-1][1]
            d2 = abs(matrix[i][j] - matrix[2][j-1]) + dp_matrix[-1][2]
            delta_i.append(min(d0, d1, d2))
        dp_matrix.append(delta_i)
    print(min(dp_matrix[-1]))

编辑于 2021-04-29 14:32:54 回复(0)