首页 > 试题广场 >

用1*3的瓷砖密铺3*20的地板有几种方式？

[单选题]
用1*3的瓷砖密铺3*20的地板有几种方式？ 
  • 1278
  • 872
  • 595
  • 406
查看答案及解析
添加回答
寄奴毓心头像 寄奴毓心
3*n的区域铺瓷砖为f(n)，如果第一列竖着，那么就是f(n-1)，如果横着铺，就是f(n-3)。
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = f(3) + f(1) =3
f(5) = f(4) + f(2) =4
f(n) = f(n-1) + f(n-3)
……
f(20) = f(19) + f(17)=1278。

发表于 2018-06-09 21:46:00 回复(4)
更多回答
chestnut7头像 chestnut7

动态规划的思想：3*n的区域铺瓷砖为f(n)，从左往右铺，如果最后一列竖着，那么就是f(n-1)，如果最后是横着铺，就是f(n-3)。
f(n) = f(n-1) + f(n-3),递推结果为1278。

发表于 2018-06-24 21:05:30 回复(0)
InFiNiTeemo头像 InFiNiTeemo
枚举横着放的瓷砖个数，利用插板法确定位置
ΣC(i,20-2*i) , i∈【0,6】 =  1278
发表于 2018-06-10 10:04:09 回复(2)
我是一座庙头像 我是一座庙
递推关系：
f(1) = 1  竖着放
f(2) = 1  竖着放
f(3) = 2  竖着or横着放
f(n) = f(n-1)+f(n-3)

直接算f(20)会很累，从f(4)算到f(20)不容易出错
发表于 2019-08-02 22:50:06 回复(2)
提交观点

问题信息

网易 算法工程师 2018
上传者：小小
难度：
4条回答 3650浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号