279.Perfect Squares
===
###### tags: `Medium`,`DP`,`Math`
[279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)

### 題目描述

Given an integer `n`, return *the least number of perfect square numbers that sum* to `n`.

A **perfect square** is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1`, `4`, `9`, and `16` are perfect squares while `3` and `11` are not.

### 範例

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

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

### 解答

#### Javascript
解法一
根據四平方和定理，每一個正整數均可以表示為4個整數的平方和。

function numSquares(n) {
  const squares = [];
  for (let i = 1; i <= n; i++) {
    if (Math.sqrt(i) % 1 === 0) {
      if (i === n) return 1;
      for (let j = 0; j < 4; j++) {
        squares.push(i);
      }
    }
  }

  // Two Sum
  let right = squares.length - 1;
  for (let i = 0; i < squares.length; i++) {
    const sum = squares[i] + squares[right];
    if (sum === n) return 2;
    if (sum > n) {
      right--;
    }
  }

  // Three Sum
  for (let i = 0; i < squares.length - 2; i++) {
    let left = i + 1;
    let right = squares.length - 1;
    while (left < right) {
      const sum = squares[i] + squares[right] + squares[left];
      if (sum === n) return 3;
      if (sum > n) {
        right--;
      } else {
        left++;
      }
    }
  }

  return 4; // 4sum沒必要
}

> [name=Marsgoat] [time= Nov 22, 2022]

解法二
跟大家學的DP

function numSquares3(n) {
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }

  return dp[n];
}

> [name=Marsgoat] [time= Nov 23, 2022]

#### Python

很慢的DP

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # init
        dp = [0] + [float("inf") for _ in range(n)]
        
        num = 1
        square_num = 1

        while (square_num <= n):
            
            # update dp array from square num
            for idx in range(square_num, n+1):
                
                dp[idx] = min(dp[idx], dp[idx - square_num] + 1)
                
            num += 1
            square_num = num* num
                
        return dp[n]
        

> [name=DT] [time= Nov 22, 2022]

依舊很慢的 DP

class Solution:
    def numSquares(self, n: int) -> int:
        table = [i for i in range(1, n+1)]
        good_point = []
        for i in range(1, n+1):
            if int(i**0.5) == i**0.5:
                table[i-1] = 1
                good_point.append(i)
            else:
                for j in good_point:
                    if table[j-1] == 1:
                        v = table[j-1] + table[i-j-1]
                        if v < table[i-1]:
                            table[i-1] = v
                        
        return table[n-1]
    

> [name=gpwork4u] [time= Nov 22, 2022]

#### C++

也很慢的DP

int numSquares(int n) {
    vector<int> dp(n+1, INT_MAX);
    dp[0] = 0;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 1; i + j * j <= n; j++)
            dp[i+j*j] = min(dp[i+j*j], dp[i]+1);
    }        
    return dp[n];
}

> [name=XD] [time= Nov 22, 2022]

### Reference

[Lagrange's four-square theorem](https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem)

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)