合計が与えられた数nと等しくなる平方数の最小個数を求めるアルゴリズム

すべての整数は、いくつかの平方数（完全平方数）の和として表すことができます。この問題では、与えられた値を表すために必要な平方数の項の最小個数を求めます。

例えば、値が95の場合、95 = 9² + 3² + 2² + 1² と表せるため、答えは4となります。

基本的な考え方は、1から順に平方数を調べていき、動的計画法（DP）によって各値ごとの最小項数を求めるというものです。値が1〜3の場合は1の二乗だけで構成するしかないため、そのまま1、2、3個の項が必要になります。

入力と出力

入力:
整数値。例えば 63。
出力:
必要な平方数の項の個数。この場合の答えは 4。
63 = 72 + 32 + 22 + 12

アルゴリズム

minSquareTerms(value)

入力: 与えられた値。

出力: その値に到達するために必要な平方数の項の最小個数。

Begin
    サイズが value + 1 の配列 sqList を定義する
    sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3 と初期化

    i が 4 から n までの間、繰り返し:
        sqList[i] := i（いったん最大値で初期化）
        x を 1 から i まで繰り返し:
            temp := x^2
            temp > i ならば
                ループを抜ける
            そうでなければ sqList[i] := min(sqList[i], 1 + sqList[i - temp])
    終了
    sqList[n] を返す
End

アルゴリズムのポイント

この手法は動的計画法に基づいています。配列 sqList[i] には「i を表すのに必要な平方数の最小個数」が格納されます。各 i について、i 以下のすべての平方数 x² を試し、「x² を1つ使った場合の残り (i − x²) の最小項数 + 1」を候補として比較します。計算量は O(n√n) となり、効率的に答えを求められます。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

int min(int x, int y) {
    return (x < y)? x: y;
}

int minSquareTerms(int n) {
    int *squareList = new int[n+1];

    // 0から3までは、すべて1^2だけで表す必要がある

    squareList[0] = 0;
    squareList[1] = 1;
    squareList[2] = 2;
    squareList[3] = 3;

    for (int i = 4; i <= n; i++) {
        squareList[i] = i; // 最初は最大値としてiを格納

        for (int x = 1; x <= i; x++) {
            int temp = x*x;     // i以下の平方数の項を見つける
            if (temp > i)
                break;
            else squareList[i] = min(squareList[i], 1+squareList[i-temp]);
        }
    }
    return squareList[n];
}

int main() {
    int n;
    cout << "Enter a number: "; cin >> n;
    cout << "Minimum Squared Term needed: " << minSquareTerms(n);
    return 0;
}

実行結果

Enter a number: 63
Minimum Squared Term needed: 4