【C++解説】nを表すために必要な最小の完全平方数の個数を動的計画法で求める

正の整数 n が与えられたとき、その和がちょうど n に等しくなるような完全平方数の最小個数を求める問題を考えます。

例えば n = 10 の場合を考えてみましょう。10 = 9 + 1 と表せるため、必要な完全平方数は 2 個となり、出力は 2 になります。

解法のアプローチ（動的計画法）

この問題は、動的計画法（DP）を使うことで効率的に解くことができます。手順は以下の通りです。

• 長さ n + 1 の DP テーブルを作成し、すべての要素を無限大（INF）で初期化する
• dp[0] = 0 と設定する（0 を作るのに必要な個数は 0）
• i = 1 から始めて、i × i ≤ n を満たす間、以下を繰り返す
  • x = i × i（現在の完全平方数）とする
  • j を x から n まで動かしながら、dp[j] を「dp[j]」と「1 + dp[j − x]」の小さい方で更新する
• 最後に dp[n] を返す

この DP の考え方は、「j という数を作るには、ある完全平方数 x を 1 つ使った残りの j − x を作る個数に 1 を加えたもの」という遷移をすべての平方数について試す、というものです。

C++での実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
public:
   int solve(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.solve(10);
}

入力

10

出力

2

コードのポイント

• 初期化： dp 配列を INF で埋めることで、「まだ到達できない状態」を明確に区別できます。
• 計算量： 外側のループは √n 回、内側のループは最大 n 回回るため、全体の時間計算量は O(n√n) となります。
• 実用性： この手法は有名な「四平方定理（ラグランジュの定理）」に関連しており、あらゆる自然数は高々 4 つの完全平方数の和で表せることが知られています。

このように、動的計画法を活用することで、一見複雑な組み合わせ最適化の問題もシンプルかつ効率的に解くことができます。