\(\mathrm{dp} _ i[j]\coloneqq 1\) 番目から \(i\) 番目の商品から価格の合計が \(j\) 円になるようにいくつか選ぶときの、選んだ商品の個数の最小値（そのような選び方が存在しないとき、\(+\infty\)）\((0\le i\le N,j\in\mathbb Z)\) と定めます。 求める答えは \(\mathrm{dp} _ N[S]\) です。

以下のような漸化式が成り立ちます。

\[\mathrm{dp} _ 0[j]=\begin{cases}0&(j=0)\\+\infty&(j\ne0)\end{cases}\] \[\mathrm{dp} _ {i+1}[j]=\min\lbrace\mathrm{dp} _ i[j],\mathrm{dp} _ i[j-A _ i]+1\rbrace\]

\(0\le j\le S\) の範囲だけを適切に計算することで、この問題を \(O(NS)\) 時間で解くことができます。

DP テーブルを使いまわし、in-place に更新を行うことで空間計算量を \(O(S)\) にすることもできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, S;
    cin >> N >> S;

    vector dp(S + 1, N + 1); // 答えの最大値は N なので、N + 1 を無限大として使う
    dp[0] = 0;
    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        // DP テーブルを更新
        for (int j = S; j >= A; --j) {
            dp[j] = min(dp[j], dp[j - A] + 1);
        }
    }

    if (dp[S] > N) { // 存在しなければ
        cout << -1 << endl; // -1
    } else { // 存在すれば
        cout << dp[S] << endl; // 答えを出力
    }
    return 0;
}

N, S= map(int, input().split())

dp = [N + 1 for _ in range(S + 1)]
dp[0] = 0

for A in map(int, input().split()):
    # DP テーブルを更新
    for i in range(S, A - 1, -1):
        dp[i] = min(dp[i], dp[i - A] + 1)

print(-1 if dp[S] > N else dp[S])