最少完美平方数分解算法 - Java 实现

最少完美平方数分解算法 - Java 实现

给定一个正整数n，找到最少数量的完美平方数（例如1, 4, 9, 16, ...），其总和为n。例如，给定n = 12，返回3，因为12 = 4 + 4 + 4; 给定n = 13，返回2，因为13 = 4 + 9。

算法思路

可以使用动态规划来解决这个问题。我们可以创建一个数组dp，其中dp[i]表示将数字i分解成完美平方数的最小数量。然后，我们可以使用以下递归公式来计算dp[i]：

dp[i] = min(dp[i], dp[i - j * j] + 1) for j = 1, 2, ..., sqrt(i)

Java 代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        
        int[] dp = new int[n + 1];
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        
        System.out.println(dp[n]);
    }
}

代码解释

1. 初始化dp数组，dp[0] = 0，因为0可以分解为0个完美平方数。
2. 循环遍历从1到n的每个数字i，计算dp[i]。
3. 对于每个i，循环遍历所有小于等于sqrt(i)的整数j，计算dp[i - j * j] + 1，并更新dp[i]为最小值。
4. 最后，dp[n]即为将n分解成完美平方数的最小数量。

示例

输入： 12

输出： 3

总结

本文介绍了使用动态规划算法解决完美平方数分解问题的Java代码实现。该算法简单易懂，时间复杂度为O(n * sqrt(n))。