2 * i的矩形可以由2 * (i - 1)的矩形竖放一块2 * 1的矩形得到,也可以由2 * (i - 2)的矩形横放两块2 * 1的矩形得到(不能计算竖放两块2 * 1的矩形,因为竖放一块时就是2 * (i - 1)的矩形,已经计算在上一种情况中了),所以写出递推式为dp[i] = dp[i - 1] + dp[i - 2],可以看出又是斐波那契,由于i = 0时约定为0,所以起始位置的情况需要单独计算。
class Solution { public: int rectCover(int number) { if (number <= 2) return number; int n1 = 1, n2 = 2, n3; for (int i = 3; i <= number; i++) { n3 = n1 + n2; n1 = n2; n2 = n3; } return n3; } };