【前言】

今天是刷题打卡第64天！

一起加油吧，嘻嘻。

原题：骨牌铺法

题目描述：

有 2*n的一个长方形方格，用一个1*2的骨牌铺满方格。请编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。

思路：

其实这道题目很简单的，找到递推公式即可，跟上面的爬楼梯问题很相似，这里就详细分析一下：

1. n = 1 时，只有一种铺法
2. n = 2 时，如下图，有全部竖着铺和横着铺两种
3. n = 3 时，骨牌可以全部竖着铺，也可以认为在方格中已经有一个竖铺的骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如下图，再无其他排列方法，因此铺法总数表示为三种。

通过上面的分析，不难看出规律：f(3) = f(1) + f(2)

所以可以的得到递推关系：f(n) = f(n - 1) + f(n - 2)

代码执行：

class Solution {
public:
    int brand(int n) {
        //找边界
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        //定义一个大小为n+1的整型数组，并且初始化为0
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i < n+1; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];//找出递推关系
        }
        return dp[n];
    }
};

结语

今天是刷题打卡第64天！

加油吧少年。