最小個数部分和問題

問題

dp[i][j]
i 番目までの整数の中から(選ぶ、選ばない)
総和が j とする方法をすべて考えたときの
選んだ整数の個数の最小値

const int INF = 1<<29; // 十分大きい値にする, INT_MAX にしないのはオーバーフロー対策

// 入力
int n, A;
int a[110];

// DPテーブル
int dp[110][10010];

int main() {
  cin >> n >> A; //個数、総和
  for (int i = 0; i < n; ++i) cin >> a[i]; //整数

  // 一旦すべて INF に
  for (int i = 0; i < 110; ++i) for (int j = 0; j < 10010; ++j) dp[i][j] = INF;
  dp[0][0] = 0;                

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]); //加算しない場合
      if (j >= a[i]) dp[i+1][j] = min(dp[i+1][j], dp[i][j-a[i]] + 1); //加算する場合
    }
  }

  if (dp[n][A] < INF) cout << dp[n][A] << endl;
  else cout << -1 << endl;
}