最大完全平方数乘积 - C++ 动态规划解法

最大完全平方数乘积 - C++ 动态规划解法

问题描述

若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数。

注意：完全平方数是非负数。

给出一个正整数 n ，从 1, 2, ..., n 中选出若干个数，使得它们的乘积是完全平方数。

求此乘积最大是多少。

解题思路

1. 首先，我们需要找出n以内的所有完全平方数。
2. 然后，我们可以使用动态规划来解决该问题。定义一个数组 dp，其中 dp[i] 表示从 1 到 i 的数中选出若干个数，使得它们的乘积是完全平方数的最大乘积。
3. 初始化 dp 数组为 0，表示从 1 到 i 的数中没有选出任何数。
4. 对于每个数 i，我们需要找到一个最大的完全平方数 j * j，使得 j * j 小于等于 i。然后，我们可以将 i 分解成两个部分，即 i = j * j * k，其中 k 为一个非完全平方数。
5. 如果 j * j * k 是一个完全平方数，那么 dp[i] = max(dp[i], dp[j * j] * dp[k])。否则，dp[i] = max(dp[i], dp[j * j]).
6. 最终，dp[n] 就是我们要求的答案。

C++ 代码实现

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int maxProduct(int n) {
    // 找出 n 以内的所有完全平方数
    vector<int> squares;
    for (int i = 1; i * i <= n; i++) {
        squares.push_back(i * i);
    }
    
    // 动态规划
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < squares.size(); j++) {
            if (squares[j] > i) {
                break;
            }
            int k = i / squares[j];
            if (k * squares[j] == i) {
                dp[i] = max(dp[i], dp[squares[j]] * dp[k]);
            }
        }
    }
    
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << maxProduct(n) << endl;
    return 0;
}

时间复杂度分析

1. 找出 n 以内的所有完全平方数的时间复杂度为 O(sqrt(n))。
2. 动态规划过程中，对于每个数 i，需要遍历完全平方数数组 squares，时间复杂度为 O(sqrt(n))。
3. 总时间复杂度为 O(sqrt(n) * sqrt(n)) = O(n)。