Số ô vuông hoàn hảo nhỏ nhất có tổng lên đến n trong JavaScript

Chúng tôi bắt buộc phải viết một hàm JavaScript nhận một số dương, chẳng hạn như num, làm đối số duy nhất.

Hàm sẽ tìm một tổ hợp các số bình phương hoàn hảo như vậy khi được thêm vào sẽ tạo ra số được cung cấp làm đầu vào. Chúng ta phải làm cho chúng ta sử dụng càng ít số lượng hình vuông hoàn hảo càng tốt.

Ví dụ -

Nếu số đầu vào là -

const num = 123;

Sau đó, kết quả đầu ra phải là -

const output = 3;

bởi vì 123 =121 + 1 + 1

Đây là một bài toán Lập trình động cổ điển trong đó chúng ta có thể đạt được kết quả cho một số cụ thể dựa trên kết quả của các số đứng trước nó.

Trước khi đi thẳng vào mã, trước tiên, hãy cố gắng hiểu một mẫu chung và DP sẽ giúp chúng ta tìm ra giải pháp như thế nào.

Kết quả cho sáu năm số sẽ là -

1 --> 1 (1)
2 --> 2 (1 + 1)
3 --> 3 (1 + 1 + 1)
4 --> 1 (4)
5 --> 2 (4 + 1)
6 --> 3 (4 + 1 + 1)

Điều này cho thấy rõ ràng chúng tôi phải cố gắng và thử kết hợp các kết quả trước để có được kết quả thành công.

Ví dụ

Sau đây là mã -

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));

Đầu ra

Sau đây là đầu ra của bảng điều khiển -

3