百度笔试 9.3 A经

第一题类似于一个均值滤波，把四舍五入处理好即可。
第二题 dfs + dp
题目描述为给你一个矩阵，可以上下左右走，也可以重复走，每次从一个格子走到另一个格子都会有一个 cost，cost的计算方法为 abs（当前格子的值 - 目标格子的值），问从左上角走到右下角的最小 cost 为多少。

样例输入：
3
1 2 4
1 3 1
1 2 1
样例输出：
2

思路：刚开始想的是直接dfs，对走过的格子进行标记，不走回头路， + 剪枝。注意这里一定是要可以上下左右走，有的最小cost路线可能是弯曲的。提交后只通过了9%，提示超时。反思应该加一个 dp，把每个点的最小 cost 记录一下，就可以大幅度剪枝。再提交就通过了。

代码：

class Solution():
    def __init__(self):
        self.res = float('inf')
        self.directions = [(0,1),(1,0),(-1,0),(0,-1)]

    def dfs(self, mat, cur_i, cur_j, cur_score, dim, dp):

        if dp[cur_i][cur_j] <= cur_score:
            return
        else:
            dp[cur_i][cur_j] = cur_score

        if cur_i == dim - 1 and cur_j == dim - 1:
            if cur_score < self.res:
                self.res = cur_score
            return
        if cur_score >= self.res:
            return

        for m, n in self.directions:
            if cur_i + m < 0 or cur_i + m >= dim or\
               cur_j + n < 0 or cur_j + n >= dim:
                continue
            if mat[cur_i + m][cur_j + n] == -1:
                continue

            val = mat[cur_i][cur_j]
            mat[cur_i][cur_j] = -1

            self.dfs(mat, cur_i + m, cur_j + n, \
                     cur_score + abs(val - mat[cur_i + m][cur_j + n]), dim, dp)

            mat[cur_i][cur_j] = val



n = int(input())
mat = []
for _ in range(n):
    mat.append(list(map(int, input().split())))

dp = [[float('inf')] * n for _ in range(n)]
s = Solution()
s.dfs(mat, 0, 0, 0, n, dp)
print(s.res)

最近笔试的场次还挺多的，今天写完后发现已经在笔试中写了很多次 dfs + dp 的题目了，并且都是最后一题。看来笔试中此类题是高频题目，还是希望大家可以掌握。