279.Perfect Squares

tags: Medium,DP,Math

279. 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沒必要
}

Marsgoat 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];
}

Marsgoat 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]
        

DT 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]
    

gpwork4u 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];
}

XD Nov 22, 2022

Reference

Lagrange's four-square theorem

回到題目列表