leetcode790:错位相减法对算法的优化

题目地址是Domino and Tromino Tiling

1
2
3
4
题目的大概意思是用
xx xx
x
两种砖块去填充一个2xn的场地,已知n时输出有多少种不同的方法。

如果都是xx的,那就是一道简单的递推。dp[n] = dp[n-1]+dp[n-2]就行了
这里加了一种不规则形状的砖块,所以又要分情况考虑

  1. dp[n] = dp[n-1]+dp[n-2]肯定需要计算在内
  2. 对于每个dp[n-k](k>=3),因为有了另一种形状的加入,从dp[n]的值还需要累加dp[n-3]…dp[0]的值并x2(这是很重要也很复杂的一点,因为这篇blog重点讲的是优化,就不展开说推论过程了)
    得出递推式是

这个递推式实现起来不难,但是因为中间有一个累加操作,所以时间复杂度是O(n^2)级别,后来看了一些题解报告,发现是可以通过数学方法优化到O(n),就是高中数学教的错位相减法,推论过程如下:

移项可得

这样子,就把时间复杂度从平方级别优化到了线性级别O(n)
效率上的提升也很直观
Markdown
另外,还可以通过矩阵乘法把代码优化到对数级别的时间复杂度,可惜线性代数的知识都要忘光了,就没有深入研究。