image.png

题目解析：注意思考如何将原问题转化为完全背包问题。

解法一（完全背包二维解法，会超时）

  • 时间复杂度：O(n n sqrt(n))

  • 空间复杂度：O(n * sqrt(n))

    1. class Solution {
    2.   public int numSquares(int n) {
    3.       //预处理范围在[1, n]内的完全平方数
    4.       List<Integer> list = new ArrayList<>();
    5.       int t = 1;
    6.       while(t * t <= n){
    7.           list.add(t * t);
    8.           t++;
    9.       }
    11.       //我们将原问题转化为：给定一个组完全平方数[1,...,sqrt(n)]，目标为n，
    12.       //求用这些数字的平方凑成n的最少数量，这个就是完全背包的最值问题了
    13.       int[][] dp = new int[(int)Math.sqrt(n) + 1][n + 1];
    15.       //由于需要我们恰好填充满背包，因为需要初始化为INF
    16.       //在此还利用了坐标偏移
    17.       //dp[0][0]代表利用0个数字凑成数值0的最少数量，当然为0
    18.       //除此之外，dp[0][1,...]均为不合法状态，初始化为INF
    19.       int INF = 0x3f3f3f;
    20.       for(int i = 0; i <= Math.sqrt(n); i++){
    21.           Arrays.fill(dp[i], INF);
    22.       }
    23.       dp[0][0] = 0;
    25.       for(int i = 1; i <= Math.sqrt(n); i++){
    26.           int val = list.get(i - 1);
    27.           for(int j = 0; j <= n; j++){
    28.               for(int k = 0; k * val <= j; k++){
    29.                   dp[i][j] = Math.min(dp[i][j], dp[i-1][j - k*val] + k);
    30.               }
    31.           }
    32.       }
    33.       return dp[(int)Math.sqrt(n)][n];
    34.   }
    35. }

解法二（完全背包问题一维解法）

  • 时间复杂度：O(n * sqrt(n))

  • 空间复杂度：O(n) ```java class Solution { public int numSquares(int n) {

      //预处理范围在[1, n]内的完全平方数
  List<Integer> list = new ArrayList<>();
  int t = 1;
  while(t * t <= n){
      list.add(t * t);
      t++;
  }

  //我们将原问题转化为：给定一个组完全平方数[1,...,sqrt(n)]，目标为n，
  //求用这些数字的平方凑成n的最少数量，这个就是完全背包的最值问题了
  int[] dp = new int[n + 1];

    int INF = 0x3f3f3f;
    Arrays.fill(dp, INF);
    dp[0] = 0;

    for(int i = 1; i <= Math.sqrt(n); i++){
        int val = list.get(i - 1);
        for(int j = 0; j <= n; j++){
            if(j - val >= 0){
                dp[j] = Math.min(dp[j], dp[j - val] + 1);
            }
        }
    }
    return dp[n];
}

} ```