[bfs & DP] 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.

정수 n이 주어지면 n의 합을 합한 최소 개수의 완전 제곱수를 반환합니다.

완벽한 정사각형은 정수의 제곱인 정수이다. 예를 들어, 1, 4, 9, 16은 완벽한 정사각형인 반면 3과 11은 그렇지 않습니다.

예시

Example 1:

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

Example 2:

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

제약

• 1 <= n <= 104

코드

• DP풀이

const numSquares = n => {
  const memo = new Array(n + 1).fill(Number.MAX_VALUE);
  memo[0] = 0;

  for (let i = 1; i <= n; i++)
    for (let j = 1; j * j <= i; j++)
      memo[i] = Math.min(memo[i], memo[i - j * j] + 1);

  return memo[n];
};

memo 배열은 perfect square의 조합으로 만들 수 있는 최소의 수 배열이다.

memo[0]은 0의 최소 조합이므로, 당연히 0

이 후, 그 자신보다 같거나 작은 perfect square의 memo값을 타고가

전부 비교해, 가장 작은 값을 계산하는 방식이다.

dp(n) : n을 완전 제곱수로 표현하기 위한 최소 개수

(점화식) dp(n) = min(dp(n-X)+1), 이때 X 는 n을 넘기지 않는 왼전 제곱 수

예를 들어 dp(13) 은 9를 완전 제곱수로 1개 선택하고 dp(13-9) + 1 = dp(4) + 1 과 같이 표현할 수 있다.