刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

编程实现：

有一个N*M的矩形拼图积木板（1≤N≤M≤15，N和M 为正整数），和若干个1*1、2*2、3*3……、10*10的正方形积木。使用任意积木将积木板铺满（不能有空隙），请问最少需要几块积木。

例如：N=3，M=4，最少需要4块积木（1块3*3，3块1*1）。

输入描述：

输入两个正整数N和M（1≤N≤M≤15），表示矩形积木板的长和宽，正整数之间以一个空格隔开

输出描述：

输出一个整数，表示铺满积木板最少需要的积木数量


样例输入：

3 4

样例输出：

4

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef min_blocks(N, M):dp = [[0] * (M + 1) for _ in range(N + 1)]for i in range(1, N + 1):for j in range(1, M + 1):dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + 1for k in range(1, min(i, j) + 1):dp[i][j] = min(dp[i][j], dp[i - k][j - k] + (k * k - k + 1) // 2)return dp[N][M]N, M = map(int, input().split())print(min_blocks(N, M))```

解析：

【喵呜刷题小喵解析】：

本题可以使用动态规划来解决。

首先，我们定义一个二维数组dp，其中dp[i][j]表示填满一个i*j的矩形所需的最少积木数。

然后，我们遍历所有可能的i和j，对于每个i和j，我们尝试使用1*1、2*2、3*3……、min(i, j)*min(i, j)的积木来填充这个矩形。

对于每个k，我们可以将i*j的矩形划分为(i-k)*(j-k)和k*k两个部分，其中k*k的部分可以用k*k个积木填充，而(i-k)*(j-k)的部分则可以使用dp[i-k][j-k]个积木填充。因此，dp[i][j]的值可以通过遍历所有可能的k，并取dp[i-k][j-k] + (k*k - k + 1) // 2的最小值来得到。

最后，我们返回dp[N][M]即可。

以上算法的时间复杂度为O(N^2*M^2)，空间复杂度为O(N*M)。由于N和M的最大值只有15，因此这个算法可以在较短时间内得到结果。
创作类型：
原创

本文链接：编程实现： 有一个N*M的矩形拼图积木板（1≤N≤M≤15，N和M 为正整数），和若干个1*1、2*

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share