【前言】

今天是刷题打卡第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天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/122010787