题解 | #最小邮票数#

最小邮票数

http://www.nowcoder.com/practice/83800ae3292b4256b7349ded5f178dd1

【C++】已通过

#include<algorithm>
using namespace std;
#define mSN minStampNum
#define ERROR 10000
int a[21];//邮票面值
int dp[101][21];
int minStampNum(int M, int N) {
	if (M < 0)return ERROR;
	//边界
	if (N == 0 && M != 0) {
		dp[M][N] = ERROR;
	}
	if (M == 0) {
		dp[M][N] = 0;
	}

	//核心递推
	if (dp[M][N] == -1) {
		dp[M][N] = min(mSN(M, N - 1), mSN(M - a[N], N - 1) + 1);
	}
	
	return dp[M][N];
	
}
int main() {
	int M, N;
	while (cin >> M >> N) {
		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 21; j++)
				dp[i][j] = -1;//刷新dp数组
		for (int i = 1; i <= N; i++) {
			cin >> a[i];
		}
		if (mSN(M, N) > N) {
			cout << 0 << endl;
		}
		else {
			cout << minStampNum(M, N) << endl;
		}
		
	}

	return 0;
}
全部评论

相关推荐

07-09 19:25
门头沟学院 Java
这是要把每一个投校招的都开盒吗?
26届之耻将大局逆转:裁人的时候一次性追回餐费
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务