Số lượng ít nhất các số chính phương tổng thành n trong JavaScript

Viết hàm nhận số dương num, tìm tổ hợp các số chính phương tổng thành num với số lượng ít nhất. Đây là bài toán quy hoạch động kinh điển.

Ví dụ: 123 → 3 (121+1+1).

Ví dụ

const num = 123;
const sumSquares = (num) => {
  let arr = new Array(num + 1).fill(0);
  arr[1] = 1;
  for (let i = 1; i * i <= num; i++) {
    for (let j = i * i; j < arr.length; j++) {
      if (arr[j] == 0) arr[j] = arr[j - i * i] + 1;
      else arr[j] = Math.min(arr[j - i * i] + 1, arr[j]);
    }
  }
  return arr[num];
};
console.log(sumSquares(num));

Kết quả

3