题目描述

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。


解题思路:

  1. dp[n]:和为 n 的完全平方数的最少数量
  2. 状态转移方程:dp[n]=1+min dp[i-j*j]
    static int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i]=min+1;
        }
        return dp[n];
    }

踩坑记录:

  1. 外层for循环控制dp[]数组从小到大,内层for计算当前dp[]数组最小值
  2. 求最小值技巧:在外层定义一个最大值,内层就可以每次对自己进行对比

Q.E.D.