C++で解く「Target Sum（ターゲットサム）」問題：動的計画法による実装方法

負でない整数のリスト a₁, a₂, ..., a_n と、目標値 S が与えられているとします。ここで使える記号は「+」と「-」の2種類であり、リスト内の各整数に対してどちらか一方を選んで割り当てる必要があります。

求めるのは、記号を割り当てた結果として整数全体の合計が目標値 S と一致するような、割り当て方の総数です。

例として、数列が [1, 1, 1, 1, 1]、S = 3 の場合を考えてみましょう。このとき出力は 5 になります。条件を満たす組み合わせは以下の通りです。

• - 1 + 1 + 1 + 1 + 1 = 3
• + 1 - 1 + 1 + 1 + 1 = 3
• + 1 + 1 - 1 + 1 + 1 = 3
• + 1 + 1 + 1 - 1 + 1 = 3
• + 1 + 1 + 1 + 1 - 1 = 3

このように、合計が 3 になる記号の割り当て方は全部で 5 通り存在します。

解法のアプローチ

この問題は、メモ化再帰（トップダウン型の動的計画法）を使うことで効率的に解けます。手順は以下の通りです。

• サイズ 21 × 2001 の DP テーブルを作成し、すべての要素を -1 で初期化します。これは計算結果をキャッシュするために使用します。
• 再帰関数 solve() を定義します。引数は現在の位置 pos、配列 v、現在の部分和 tempSum、そして目標値 s です。
• pos が配列 v のサイズと等しくなったら、s == tempSum であれば 1（true）、そうでなければ 0（false）を返します。
• dp[pos][tempSum + 1000] が -1 以外であれば、その値をそのまま返します（メモ化により再計算を回避）。
• ans := solve(pos + 1, v, tempSum - v[pos], s) + solve(pos + 1, v, tempSum + v[pos], s) として、「-」を付けた場合と「+」を付けた場合の両方を探索します。
• 結果を dp[pos][tempSum + 1000] に保存してから返します。
• main 部分から solve(0, nums, 0, s) を呼び出します。

なお、tempSum に 1000 を加算しているのは、部分和が負の値になる可能性があるため、インデックスとして扱えるようにオフセットを設けているためです。

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int dp[21][2001];
   int solve(int pos, vector <int> v, int tempSum, int s){
      if(pos == v.size()){
         return s == tempSum;
      }
      if(dp[pos][tempSum+1000]!=-1)return dp[pos][tempSum+1000];
      int ans = solve(pos+1,v,tempSum-v[pos],s) +solve(pos+1,v,tempSum+v[pos],s);
      dp[pos][tempSum+1000] = ans;
      return ans;
   }
   int findTargetSumWays(vector<int>& nums, int s) {
      int n = nums.size();
      if(s>1000)return 0;
      for(int i =0;i<21;i++){
         for(int j =0;j<2001;j++){
            dp[i][j] = -1;
         }
      }
      return solve(0,nums,0,s);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1,1,1};
   cout << ob.findTargetSumWays(v, 3);
}

入力

[1,1,1,1,1]
3

出力

5

この実装では、全組み合わせを素朴に列挙すると O(2^n) かかるところを、メモ化によって重複する状態の計算を省略できるため、大幅な高速化が実現できます。