JZ10 矩形覆盖

题解

function rectCover(number)
{
    if(number === 0 || number === 1){
        return number
    }
    let dp = new Array(number + 1).fill(0)
    dp[0] = 1
    dp[1] = 1
    
    for(let i = 2; i < number + 1; ++i){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    
    return dp[number]
}

解法

解法本质上和跳台阶一样，以number == 3的情况为例,dp[i]代表有i个位置时摆放方式

1. 左侧第一个方块竖着放，右边还剩两个空方块，此时有几种摆放方式呢？显然是dp[2],因为左边确定是竖着，只要考虑右边空着的位置即可
2. 左侧横着，那左侧就需要两个方块，此时右边还剩一个空的，此时的摆放方式就是dp[1],因为左边两个确定了。
   那dp[3] = dp[2] + dp[1],对于dp[4]也是一样的做法。因此dp[i] = dp[i - 1] + dp[i - 2]