JavaScriptで合計がnになる最小数の完全な平方

唯一の引数として正の数、たとえばnumを受け取るJavaScript関数を作成する必要があります。

関数は、追加されたときに入力として提供された数を与えるような完全な平方数の組み合わせを見つける必要があります。使用する完全な正方形の数をできるだけ少なくする必要があります。

例-

入力番号が-

const num = 123;

その場合、出力は-

const output = 3;

123 =121 + 1 + 1

これは古典的な動的計画法の問題であり、前の数値の結果に基づいて特定の数値の結果に到達できます。

コードに直接飛び込む前に、まず一般的なパターンを理解してみてください。実際、DPはソリューションの考案に役立ちます。

6つの5つの数値の結果は-

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

これは、次の結果を得るために、前の結果で組み合わせを試してみる必要があることを明確に示しています。

例

以下はコードです-

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

出力

以下はコンソール出力です-

3