題目背景

uim 神犇拿到了 uoi 的 ra（鐳牌）后，立刻拉著基友小 A 到了一家……餐館，很低端的那種。

uim 指著墻上的價目表（太低級了沒有菜單），說：“隨便點”。

題目描述

不過 uim 由于買了一些書，口袋里只剩?M?元?(M≤10000)。

餐館雖低端，但是菜品種類不少，有?N?種?(N≤100)，第?i?種賣?ai??元?(ai?≤1000)。由于是很低端的餐館，所以每種菜只有一份。

小 A 奉行“不把錢吃光不罷休”的原則，所以他點單一定剛好把 uim 身上所有錢花完。他想知道有多少種點菜方法。

由于小 A 肚子太餓，所以最多只能等待?1?秒。

輸入格式

第一行是兩個數字，表示?N?和?M。

第二行起?N?個正數?ai?（可以有相同的數字，每個數字均在?1000?以內）。

輸出格式

一個正整數，表示點菜方案數，保證答案的范圍在 int 之內。
上代碼！

#include <bits/stdc++.h>
using namespace std;
int dp[1010];
int s[1010];
int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];}dp[0]=1;for(int i=1;i<=n;i++){for(int j=m;j>=s[i];j--){dp[j]+=dp[j-s[i]];}}cout<<dp[m];
}