今天的一道头条面试题

# coding = utf-8 def mul(m1, m2):     h1, w1 = len(m1), len(m1[0])     h2, w2 = len(m2), len(m2[0])     result = [[0]*w2 for _ in range(h1)]     for i in range(h1):         for j in range(w2):             result[i][j] = sum([m1[i][k]*[v[j] for v in m2][k] for k in range(w1)])     return result def quick(m, n):     result = m     n -= 1     while n:         if n&1:             result = mul(result, m)         m = mul(m, m)         n >>= 1     return result def f(w):     memo = [0] * w     memo[0] = 1     memo[1] = 2     memo[2] = 4     for i in range(3, w):         memo[i] = memo[i-1]+memo[i-2]+memo[i-3]     return memo[-1] param = [[1,1,1], [1,0,0], [0,1,0]] # 初始化 w, h = 10, 4   r = quick(param, w-3) r = mul(r, [[4], [2], [1]])[0][0] print(r)  # 矩阵快速幂方法 # print(f(10))  # 动态规划 total_number = r**h

H多大啊，是不是固定的啊

类似斐波那契数列吧

1*3这个砖块推起来好像很复杂的样子

当H为1时 就是裴波那契数列题目 得到m种方法，所以最后有m^h种方法？？？

最小时间复杂度可以达到 log2N？？

对于f(n)=f(n-1)+f(n-2)+f(n-3)这个可以用构造转移矩阵，然后矩阵快速幂的方法做，可以上网搜斐波那契的矩阵快速幂做法，这个没学过的一般想不到，拿着个考人有点儿。。