阿里 3月25日笔试第一题

题目描述：

给定一个 3 * n 的矩阵，从每列选取一个元素组成一个新的长度为 n 的数组。求此数组前后元素之间差值的绝对值之和最小。

示例：

5 9 5 4 4
4 7 4 10 3
2 10 9 2 3
结果为 5。选取的元素为 5 7 5 4 4

这题一开始我用的贪心，浪费了十多二十分钟才发现不能直接贪。。
然后二话不说就开始回溯，然后我本来写回溯就要很久。。然后又出了各种 bug 调试了半天最后没时间了。。。回溯写出来应该是对的，但是跑到 30% 的时候就爆栈了。。然后也没时间再慢慢思考了。。。所以说做 OJ 还是不要轻易用回溯。

所以这道题应该用动规。。

n = int(input())

b = []
for i in range(3):
    a = list(map(int, input().split(' ')))
    b.append(a)


dp = [[0 for i in range(n)] for j in range(n)]


for j in range(1, n):
    for i in range(3):
        dp[i][j] = min(abs(b[i][j] - b[0][j - 1]) + dp[0][j - 1], abs(b[i][j] - b[1][j - 1]) + dp[1][j - 1], 
                        abs(b[i][j] - b[1][j - 1]) + dp[1][j - 1])
        
print(min(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]))

下来之后回想还是挺简单的。。但是我做算法题本来就比较慢，思考要思考半天。。感觉再怎么刷题也没办法提升我的速度。。然后还有时间限制，就更慌了。。。

不该啊不该。。什么时候才能身经百战游刃有余。。。。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

阿里 3月25日 笔试第一题

阿里 3月25日笔试第一题