279. Perfect Squares

Question

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Thinking:

  • Method 1: dp
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++){
            int res = Integer.MAX_VALUE;
            for(int j = 1; j * j <= i; j++){
                res = Math.min(res, dp[i - j * j] + 1);
            }
            dp[i] = res;
        }
        return dp[n];
    }
}

Second time

  • Method 1 dp
    1. Set all integer squares smaller than n to 1.
    2. Initial all other values to MAX_VALUE.
    3. for each number, if dp[i] == 1, skip, else check all add combination of the values and take the minimum value. 
      class Solution {
 public int numSquares(int n) {
     int[] dp = new int[n + 1];
     for(int i = 0; i <= n; i++){
         dp[i] = Integer.MAX_VALUE;
     }
     for(int i = 1; i * i <= n; i++){
         dp[i * i] = 1;
     }
     for(int i = 2; i <= n; i++){
         if(dp[i] == 1) continue;
         for(int j = i / 2; j >= 1; j--){
             dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
         }
     }
     return dp[n];
 }
}
  • Method 2 dp 
    class Solution {
  public int numSquares(int n) {
      int[] dp = new int[n + 1];
      for(int i = 1; i <= n; i++){
          int res = Integer.MAX_VALUE;
          for(int j = 1; j * j <= i; j++)
              res = Math.min(res, dp[i - j * j] + 1);
          dp[i] = res;
      }
      return dp[n];
  }
}