题解 | #矩形覆盖#

矩形覆盖

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

思路

把数字翻译成字符串差不多的思路,该时刻的dp值前两个时刻的dp值有关

状态转移

这里的状态转移如下:

dp[i] = dp[i-1] + dp[i-2]

但是本质思想并不是简单的把前两个时刻相加,它的两个部分分别解释为:

  1. 对于只有一个空位的话,只能又一种方法,所以是dp[i-1]
  2. 对于能够有2个空位的话,其实有横着和竖着2种方法填补的,所以感觉上是dp[i-2] * 2,但是注意到这种情况下,如果在往前一个空位的情况下是一个竖条,那剩下的2个空位也都是竖条的话,那么就和解释1.中出现了重复的情况,所以不能是dp[i-2]

因此最终的状态转移形式就是看到的把前两个时刻相加。

全部评论

相关推荐

28小凳也想实习:项目不用一个业务一个轮子吗,刷牛客好多人说要一业务一轮子
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务