m*n长方形中正方形最少个数 cpp

要求 m*n 的长方形中最少需要多少个正方形来填满，可以使用动态规划的思想，令 dp[i][j] 表示填满 i*j 的长方形最少需要的正方形个数。

状态转移方程为：

dp[i][j] = min(dp[i-k][j]+dp[k][j-k])，其中 1<=k<=i/2

dp[i][j] = min(dp[i][j-k]+dp[i-k][k])，其中 1<=k<=j/2

初始状态为 dp[i][i] = 1，dp[i][j] = INT_MAX，其中 INT_MAX 表示一个很大的数。

最终答案为 dp[m][n]。

以下是用 C++ 实现的代码：

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

const int N = 505;
int dp[N][N];

int main()
{
    int m, n;
    cin >> m >> n;

    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= max(m, n); i ++)
        dp[i][i] = 1;

    for(int i = 1; i <= m; i ++)
        for(int k = 1; k <= i / 2; k ++)
            dp[i][n] = min(dp[i][n], dp[i-k][n] + dp[k][n-i+k]);

    for(int j = 1; j <= n; j ++)
        for(int k = 1; k <= j / 2; k ++)
            dp[m][j] = min(dp[m][j], dp[m][j-k] + dp[m-k][k]);

    cout << dp[m][n] << endl;

    return 0;
}