题解 | #最小邮票数#

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N]; // 价格 
int f[N][N]; // 前i张邮票凑成j分的最小张数
// f[0-n][0] = 0;
// f[0][1-m]
 
int main(){
	
	int m; //总值
	int n; // 邮票数

	cin >> m >> n;
	memset(f, 0x3f, sizeof(f));
	for (int i=1; i<=n; i++){
		cin >> w[i];
	}
	for (int i=0; i<=n; i++){
		f[i][0] = 0;
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if (j < w[i]){
				f[i][j] = f[i-1][j];
			}
			else{
				f[i][j] = min(f[i-1][j], f[i-1][j-w[i]] + 1);
			}
		}
	}
		
	if (f[n][m] == 0x3f3f3f3f){
        // puts("0");
        puts("0");
       }
    else{
        printf("%d\n", f[n][m]);
    }

	return 0;
}