矩形覆盖问题

矩形覆盖

http://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6

简单的递归

  • 当n=1时,只能竖着覆盖,f(1)=1;

  • 当n=2时,既可以横着覆盖,也可以竖着覆盖,f(2)=2;

  • 当n=N时,只需要考虑第一块如何覆盖即可,详见下图:
    图片说明

  • 代码如下:

      public int rectCover(int target) {
    
          if (target <= 0) {
              return 0;
          }
          if (target == 1) {
              return 1;
          }
          if (target == 2) {
              return 2;
          }
          return rectCover(target - 1) + rectCover(target - 2);
      }
    
全部评论
虽然这个结果是对的 但是我感觉这个情况考虑的不对 如果竖着放 你还要考虑放在前面和后面这两种情况 虽然会有重复的 但是确实会多出来一种新的情况 那么对于n=4来说 实际最后计算应该是 4种(竖放)+1种(横放)而不应该是f(3)+f(2)=3种+2种
1 回复 分享
发布于 2020-11-17 19:44
这样会导致重复计算
1 回复 分享
发布于 2020-07-31 09:42
懂了
点赞 回复 分享
发布于 2024-08-29 23:12 上海
请问这样不会超时吗
点赞 回复 分享
发布于 2020-06-23 09:33
图片很直观了,感谢
点赞 回复 分享
发布于 2020-04-24 14:57
f(n-2)的图有点问题吧
点赞 回复 分享
发布于 2020-02-29 22:58

相关推荐

03-27 16:40
已编辑
门头沟学院 C++
26学院本太难了,很多公司机筛就给我刷了。机会都难拿到如果是简历存在问题也欢迎拷打————————————————————分割线——————————————————————2026.3.4更新:发完贴之后,时不时投递又收到了不少的笔试/面试邀请。主要是之前投递简历出去之后基本上都是沉默状态,年后好转了不少timeline:2026.01.21&nbsp;文远知行笔试,半年多没刷算法题&nbsp;-&gt;挂&nbsp;(后续HR说春招可以重新安排笔试)2026.2.4&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;小鹏汇天&nbsp;技术一面,第二周收到结果&nbsp;-&gt;挂2026.2.12&nbsp;&nbsp;&nbsp;大众Cariad代招&nbsp;技术二面&nbsp;-&gt;Offer2026.2.28&nbsp;&nbsp;&nbsp;多益网络技术面试,由于风评太差,一直在犹豫要不要接面试&nbsp;-&gt;推迟-----------分割线-----------2026.3&nbsp;月前的某一天,临时去电网报名了二批计算机岗位的笔试2026.3.6&nbsp;从上家公司实习离职,氛围最好的一家公司,leader&nbsp;说可以帮忙转正,但是流程太长,而且我们部门据说只有一个&nbsp;hc,更想要研究生,我很有可能是会被签外包公司在这里干活,就离职了。2026.3.9&nbsp;入职新公司,大众Cariad&nbsp;以外部公司的身份进组,项目组签了三年,后续三年应该都可以在这里呆,不知道有没有希望原地跳槽。2026.3.10&nbsp;电网考试居然说我通过资格审查了,短信约我去参加资格审查,请假一天,买了&nbsp;12&nbsp;号晚上的机票回成都2026.3.15&nbsp;参加国家电网计算机类笔试2026.3.17&nbsp;电网出成绩了,感觉很低。觉得已经🈚️了2026.3.18&nbsp;收到电网面试通知,通知&nbsp;3.22-3.25&nbsp;这个时间去面试,我的岗位只招&nbsp;1&nbsp;个人。据说面试只有&nbsp;2-3&nbsp;人,不知道能不能成功----------分割线-----------2026.3.21&nbsp;电网面试结束,感觉回答的还勉勉强强,大概是2个岗位分别招1个人,一共11人面试,实际来了9人2026.3.27&nbsp;出面试成绩,满分100分,早上10:20左右发现面试成绩46,我震惊了,没截图,后面过了十分钟重新看发现面试成绩给我改成58了。但同样震惊。朋友问我是不是把面试官打了,哈哈
点赞 评论 收藏
分享
评论
63
3
分享

创作者周榜

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