时间复杂度$O(nm)$

空间复杂度$O(m)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1010 , M = 1e4 + 10 ; 

int f[M] ;
// f[i , j] 表示前 i 种纸币凑出金额为 j 的最少数量
int n , m , a[N] ;

int main(int argc, char const *argv[])
{
	cin.tie(nullptr)->ios::sync_with_stdio(false) ;
	cin >> n >> m ;
	for(int i = 1 ; i <= n ; ++ i) cin >> a[i] ;
	memset(f , 0x3f , sizeof f) ; 
	f[0] = 0 ; 
	for(int i = 1 ; i <= n ; ++ i) 
		for(int j = a[i] ; j <= m ; ++ j)
			f[j] = min(f[j] , f[j - a[i]] + 1) ;

	cout << f[m] << '\n' ;
	return 0;
}