题目：我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，总共有多少种方法？
思路：覆盖一个 2 * n，（n>=3） 的大矩形的方法数等于
1)使用一个2 * 1 的小矩形竖放在最左边，剩下的部分相当于覆盖一个 2 *（n-1） 的大矩形的方法
2）使用两个2 * 1 的小矩形横放在最左边，剩下的部分相当于覆盖一个 2 * （n-2） 的大矩形的方法
即f(x) = f(x-1) + f(x-2)
再处理好边界值，f(0)=0, f(1)=1, f(2)=2
Python代码如下：
class Solution:
def rectCover(self, number):
dp = [0, 1, 2]
for n in range(3, number+1):
dp.append(dp[n-1]+dp[n-2])
return dp[number]
题目：我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2 * 1 的小矩形无重叠地覆...
《剑指offer》面试题10（题目二）相关题目：矩形覆盖 题目：我们可以用2 x 1的小矩形横着或者竖着去覆盖更大...
本文首发于我的个人博客：尾尾部落 题目描述 我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2...
本文首发于我的个人博客Suixin’s Blog原文: https://suixinblog.cn/2019/03...
写在前面： 为了增长一下自己的数据结构能力，也为了面试准备，准备将剑指Offer做一下，并与各位分享，希望各位可以...
题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总...
题目 我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×1的小矩形无重叠地覆盖一个2×n的大矩形...
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多...
10. 矩形覆盖 题目描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖...
题目描述 矩形覆盖 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*...
本文标题：剑指offer面试题09-4----矩形覆盖
本文链接：https://www.haomeiwen.com/subject/ydedlxtx.html
网友评论