递推

• 是按照一定的规律来计算序列中的每个项,通常是通过计算前面的一些项来得出序列中的指定项的值.
• Eg: a[i]=a[i-1]+a[i-2] //斐波那契数列
• Tip: 递推时要给一些特殊情况赋初值
• 例题:

题目描述

使用1_2的小矩阵去填满3_n的大矩阵,要使得刚好铺满,问有多少种方案.

输入

输入n,n为偶数, 2<=n<=28

输出

输出方案数

样例输入

4

样例输出

11

思路

大致可以描述为:保证宽都是 3 的情况下,最后一步长为 2 的有 3 种,长为 4, 6, 8, …的各有 2 种方案.
那么,递推方程为: f[i]=f[i-2]*3+f[i-4]*2+….+f[2]*2+f[0]*2 (1)
对(1)式扩展一步得到: f[i+2]=f[i]*3+f[i-2]*2+…+f[2]*2+f[0]*2 (2)
(2) -(1)得到: f[i+2]-f[i]=f[i]*3-f[i-2] (3)
(3) 移项得: f[i+2]=f[i]*4-f[i-2] (4)
(4)的结果等效于: f[i]=f[i-2]*4-f[i-4],即为本题递推公式.

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/26/