题解 | #最小邮票数#
最小邮票数
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;
}
查看30道真题和解析
投递小鹏汽车等公司7个岗位