矩形覆盖

矩形覆盖

https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&tqId=11163&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

比如n=3时,2*3的矩形块有3种覆盖方法:
图片说明

这道题仔细分析还是爬楼梯问题,要得到长度为n的2n矩形,可以是通过添加2(n-1)的矩形一个竖着的12矩形得到,也可以是通过在2(n-2)的基础上添加两个横着的矩形得到。
所以得到状态转移方程为f(i) = f(i-1) + f(i-2)。

全部评论

相关推荐

牛客76783384...:字节:不要放箭,活捉赵子龙
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务