### gọi dp[i] là số lượng đồng xu ít nhất phải dùng để đủ tổng i
#### trường hợp cơ sở dp[0] = 1, dp[i] = INF, ∀ i > 0
- duyệt $\ i: 1 \to k \$
- với mỗi i duyệt $\ j: 1 \to n \$ , nếu nó thỏa $coin[j] \leq i$ thì tương đương có cách chọn coin[j] vào tổng i
- nhưng vì yêu cầu lấy đồng xu ít nhất nên ta sẽ lấy min của (dp[i], dp[i - coin[j]] + 1)
dp[k] chính là kết quả bài toán, nếu nó bằng INF tương đương không có cách nào in -1
code:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define el "\n"
using namespace std;
const ll maxN = 1e5 + 5;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, k; cin >> n >> k;
vector <ll> coin(n + 1), dp(k + 1, llmax - 1);
for(int i = 1 ; i <= n; i++) cin >> coin[i];
dp[0] = 0;
for(int i = 1; i <= k; i++) {
for(int j = 1; j <= n; j++) {
if(coin[j] <= i) dp[i] = min(dp[i], dp[i - coin[j]] + 1);
}
}
cout << (dp[k] >= llmax - 1 ? -1 : dp[k]);
}
```
Long4200
Created at
0 likes