C++で完全平方数の和に分解する：最小個数を求める動的計画法の解説

正整数 n が与えられたとき、その値を完全平方数（1、4、9、16…など）の和として表現するために必要な「最小の個数」を求める問題を考えてみましょう。

例えば n = 13 の場合、13 = 9 + 4 と表せるため、答えは 2 となります。この記事では、この問題をC++で効率的に解くための動的計画法（DP）のアプローチを詳しく解説します。

アルゴリズムの考え方

この問題は、コイン払い戻し問題と同じ構造を持っています。「各完全平方数」をコインとみなし、金額 n を作るのに必要な最小のコイン枚数を求めるイメージです。解法の手順は以下の通りです。

• 長さ n + 1 のDPテーブルを作成し、すべての要素を無限大（INF）で初期化します
• dp[0] := 0 と設定します（0を作るのに必要な個数は0個）
• i = 1 から開始し、i * i <= n である間、以下を繰り返します
• • x = i * i（i番目の完全平方数）とします
  • j を x から n まで動かしながら、dp[j] := min(dp[j], 1 + dp[j − x]) で更新します
• 最後に dp[n] を返します

この更新式は、「j を作るには、(j − x) を作る方法に x を1つ加える」ことを意味しており、既存の最小値と比較してより小さい方を採用します。

C++での実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
   public:
   int numSquares(int n) {
      vector < int > dp(n+1,INF);
      dp[0] = 0;
      for(int i =1;i*i<=n;i++){
         int x = i*i;
         for(int j = x;j<=n;j++){
            dp[j] = min(dp[j],1+dp[j-x]);
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numSquares(147));
}

入力

147

出力

3

実行結果の解説

n = 147 の場合、出力は 3 となります。これは例えば 147 = 49 + 49 + 49（= 7² + 7² + 7²）のように、3つの完全平方数の和で表せることを示しています。

このアルゴリズムの計算量は外側のループが O(√n)、内側のループが O(n) であるため、全体で O(n√n) となり、n が大きくなっても十分実用的な速度で動作します。また、空間計算量はDPテーブル分の O(n) です。