字节1015算法笔试ak

第一题证明一下排序后最后位置最小就行，第二题用个defaultdict存就行，第三题check二分从最大最小开始搜不同的位置，然后每个候选x去判断就行。

其他都比较简单，就记录一下第四题吧

小红拿到了一个n阶正方形矩阵{aij}，他准备从左上角走到右下角，每一步可以向右或向下走一格，向知道有多少种不同路径满足路径元素和恰好为x。

0<x,aij<10^9

1<n<18

注解：dp肯定能想到，首先必须用稀疏方式存储路径值，不然开三维数组内存爆炸时间太长。其次如果不剪枝只能过一半，剪枝两种方法，一种如果当前值已经超了，就不计算路径数量了；另一种计算当前位置到终点的最大路径，如果当前值加上最大路径还是不够，直接剪掉。

from collections import defaultdict
n,x = map(int,input().split())
mat = []
for i in range(n):
    mat.append(list(map(int,input().split())))
dp = [[defaultdict(int) for _ in range(n)] for __ in range(n)]
dp[0][0][mat[0][0]] = 1
leng = [[0 for _ in range(n)] for __ in range(n)]
leng[-1][-1] = mat[-1][-1]
for i in range(n-1,-1,-1):
    for j in range(n-1,-1,-1):
        if i == n - 1 and j == n - 1:
            continue
        if i == n - 1:
            leng[i][j] = leng[i][j+1] + mat[i][j]
        elif j == n - 1:
            leng[i][j] = leng[i+1][j] + mat[i][j]
        else:
            leng[i][j] = max(leng[i][j+1],leng[i+1][j]) + mat[i][j]
for i in range(n):
    for j in range(n):
        if i > 0:
            for key,value in dp[i-1][j].items():
                if key + mat[i][j] > x or key + leng[i][j] < x:
                    continue
                dp[i][j][key + mat[i][j]] += value
        if j > 0:
            for key,value in dp[i][j-1].items():
                if key + mat[i][j] > x or key + leng[i][j] < x:
                    continue
                dp[i][j][key + mat[i][j]] += value
print(dp[-1][-1][x])