题解 | #兑换零钱#
兑换零钱
https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,aim;
scanf("%d %d\n",&n,&aim);
vector<int> dp(aim+1,INT_MAX-1);
dp[0] = 0;
for(int i=0;i<n;i++) {
int item;
scanf("%d",&item);
for(int j=item;j<=aim;j++)
dp[j] = min(dp[j],dp[j-item]+1);
}
printf("%d\n",dp[aim]==INT_MAX-1? -1:dp[aim]);
return 0;
}
算法常用解题技巧 文章被收录于专栏
算法常用解题技巧
查看20道真题和解析