看铺砖师傅的手法就知道专业_川式炸匠铺·红小六怎么样

看铺砖师傅的手法就知道专业_川式炸匠铺·红小六怎么样鉴于多次遇到铺砖问题,因此目前遇到对此类问题进行总结:铺砖问题主要分类:1.简单的一维铺砖问题2.二维铺砖问题2*1的砖是否可以铺满N*M的地面3.二维铺砖铺满有多少种方法a.2*1的砖铺满2*M

看铺砖师傅的手法就知道专业_川式炸匠铺·红小六怎么样"

鉴于多次遇到铺砖问题,因此目前遇到对此类问题进行总结:

铺砖问题主要分类:

1.简单的一维铺砖问题

2.二维铺砖问题

                 2*1的砖是否可以铺满N*M的地面

3.二维铺砖铺满有多少种方法

                a.2*1的砖铺满2*M的地面有多少种方法?

                b. 2*1的砖铺满N*M的地面有多少种方法?

 

『简单的一维铺砖问题』

【问题描述】
  有一长度为N(1<=N<=10)的地板,给定两种不同瓷砖:一种长度为1,另一种长度为2,数目不限。要将这个长度为N的地板铺满,一共有多少种不同的铺法?(蓝桥杯算法训练试题)

【解题思路】

      一道简单的递推或者说是DP的题目

     N = 1时,只有一种方法 一块长为1的砖

     N = 2时,两种方法 两块长为1的砖,一块长为2的砖

     N = 3时,三种方法  三块长为1的砖,先一块长为1的砖,后一块长为2的砖,先一块长为2的砖,后一块长为1的砖。

     以N=3举例,我们可以这样看

                   a.先铺好了一块1格的地面,那么再铺一块长为2的砖就可以达到3格

                   b.先铺好了一块2格的地面,那么再铺一块长为1的砖就可以达到3格

     即第i格地面的铺设方式为  第i-1和第i-2的方式的和。

     从上面我们可以逐渐发现递推公式  或  状态转移方程  :dp[i] = dp[i-1]+d。p[i-2];

【代码】

#include <bits/stdc++.h>
using namespace std;
int dp[50];
int main()
{
    int n;
    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= 40; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout << dp[n];
    return 0;
}

『二维是否可铺满问题』

【问题描述】

某年夏天,位于希格玛大厦四层微软亚洲

今天的文章看铺砖师傅的手法就知道专业_川式炸匠铺·红小六怎么样分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67963.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注