题解 | #矩形覆盖#
矩形覆盖
http://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6
思路
与把数字翻译成字符串差不多的思路,该时刻的dp值
与前两个时刻的dp值
有关
状态转移
这里的状态转移如下:
dp[i] = dp[i-1] + dp[i-2]
但是本质思想并不是简单的把前两个时刻相加,它的两个部分分别解释为:
- 对于只有一个空位的话,只能又一种方法,所以是
dp[i-1]
。 - 对于能够有2个空位的话,其实有横着和竖着2种方法填补的,所以感觉上是
dp[i-2] * 2
,但是注意到这种情况下,如果在往前一个空位的情况下是一个竖条,那剩下的2个空位也都是竖条的话,那么就和解释1.中出现了重复的情况,所以不能是dp[i-2]
。
因此最终的状态转移形式就是看到的把前两个时刻相加。