有一块大小是 2 * n 的墙面,现在需要用2种规格的瓷砖铺满,瓷砖规格分别是 2 * 1 和 2 * 2,请计算一共有多少种铺设的方法。
时间: 2023-06-05 16:47:17 浏览: 274
行业文档-设计装置-一种瓷砖饰面组合墙体板.zip
这道题目是一道典型的动态规划问题。我们可以用 dp[i] 表示铺满 i * 2 的墙面有多少种方法,那么 dp[i] 的值可以由 dp[i-1] 和 dp[i-2] 推导出来。
当我们铺满 i-1 * 2 的墙面后,只有一种铺法可以将最后一列铺上 2 * 1 的瓷砖,此时 dp[i] = dp[i-1]。
当我们铺满 i-2 * 2 的墙面后,有两种铺法可以将最后两列铺上瓷砖,一种是铺上两个 2 * 1 的瓷砖,另一种是铺上一个 2 * 2 的瓷砖。因此 dp[i] = dp[i-1] + dp[i-2]。
最终的答案就是 dp[n]。
代码如下:
int dp[100];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
阅读全文