鉴于多次遇到铺砖问题,因此目前遇到对此类问题进行总结:
铺砖问题主要分类:
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