Өгсөн зоосуудаар мөнгийг хамгийн цөөн зоосоор бүрдүүлнэ. Жижиг мөнгөнөөс эхлэн хүснэгт бөглөдөг DP бодлого.

IntermediateХугацаа: O(n · s)Санах ой: O(s)
HackerRank дээр бодох

Эхлээд жижиг бодлого

1, 3, 4 төгрөгийн зоос байна, зоос бүрээс хэдийг ч авч болно. 6 төгрөгийг хамгийн цөөн зоосоор бүрдүүлье.

Хамгийн томоос нь авбал 4 + 1 + 1, гурван зоос. Гэтэл 3 + 3 гэвэл хоёрхон зоос. Хариу 2.

Энгийн аргаас санаа руу

Эхний санаа бол Greedy: үргэлж багтах хамгийн том зоосыг авах. Дээрх жишээнд энэ нь алдлаа. Бүх хослолыг шалгах нь зөв ч хэтэрхий удаан.

Гол санаа нь сүүлийн зоос. x төгрөгийг бүрдүүлэхдээ хамгийн сүүлд c[i] зоос нэмсэн гэж үзье. Тэгвэл өмнө нь x - c[i] төгрөгийг хамгийн цөөн зоосоор бүрдүүлсэн байх ёстой. Тиймээс dp[x] = min(dp[x - c[i]] + 1), бүх зоосоор. x-ийг 1-ээс s хүртэл дарааллаар бодвол dp[x - c[i]] үргэлж бэлэн байна.

Нэр томьёо ба тэмдэглэгээ

dp[x]
State: x төгрөгийг бүрдүүлэх хамгийн цөөн зоосны тоо.
INF
1e9. "Одоохондоо бүрдүүлж чадахгүй" гэсэн утга. Хариу хэзээ ч ийм их болохгүй.
c[i]
i-р зоосны үнэ. Transition-д сүүлийн зоос болж туршигдана.
Greedy
Тухайн мөчид хамгийн сайн харагдах сонголтыг хийдэг арга. Энэ бодлогод зарим зоосны багцад алддаг.
c
1
0
3
1
4
2
dp
0
0
1
2
3
4
5
6

6 төгрөгийг 1, 3, 4 төгрөгийн зоосоор бүрдүүлнэ. Зоос бүрээс хэдийг ч авч болно. Хамгийн цөөндөө хэдэн зоос хэрэгтэй вэ? State: dp[x] нь x төгрөгийг бүрдүүлэх хамгийн цөөн зоосны тоо.

Алхам 1 / 16
Хурд
  • Бодож буй dp[x]
  • Зоос ба dp[x − c[i]]
  • ∞: одоохондоо бүрдэхгүй
  • Бэлэн
  • Хариу
Слайд 1 / 6

Хамгийн цөөн зоос

1, 3, 4 төгрөгийн зоосоор 6 төгрөг бүрдүүлье. Хамгийн томоос нь эхэлбэл 4 + 1 + 1 буюу гурван зоос болно. Гэтэл 3 + 3 гэвэл хоёрхон зоос. Томыг нь түрүүлж авдаг Greedy арга энд алдлаа.

coin-change.cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, s, c[105], dp[1000005];
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) cin >> c[i];
dp[0] = 0;
for (int x = 1; x <= s; x++) dp[x] = INF;
for (int x = 1; x <= s; x++) {
for (int i = 0; i < n; i++) {
if (c[i] <= x) {
dp[x] = min(dp[x], dp[x - c[i]] + 1);
}
}
}
cout << (dp[s] == INF ? -1 : dp[s]) << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Хамгийн том зоосыг түрүүлж авдаг Greedy арга үргэлж зөв биш гэдгийг харна. Харин DP хүснэгт үргэлж зөв хариу өгнө. HackerRank дээрх "The Coin Change Problem" бол бүрдүүлэх аргын тоог олдог хувилбар.

Яаж ажилладаг вэ?

1. State: dp[x] нь x төгрөгийг бүрдүүлэх хамгийн цөөн зоосны тоо. dp[0] = 0, бусад нь эхлээд ∞. 2. x = 1, 2, …, s гэж дарааллаар нь бодно. 3. Transition: c[i] ≤ x бол сүүлийн зоос нь c[i] байж болно. dp[x] = min(dp[x], dp[x − c[i]] + 1). 4. dp[s] нь ∞ хэвээр байвал бүрдүүлэх боломжгүй, хариу −1. Оролт: эхний мөрөнд зоосны төрлийн тоо n ба мөнгө s, дараагийн мөрөнд n зоос.

Яагаад зөв, хэр хурдан бэ?

Хамгийн цөөн зоостой ямар ч хариунаас сүүлийн зоосыг аваад хаявал үлдсэн нь x - c[i] төгрөгийн хамгийн цөөн хариу байх ёстой. Үгүй бол түүнийг сайжруулаад x-ийн хариуг ч сайжруулж чадах байсан. Код бүх c[i]-г туршдаг тул тэр хамгийн сайн сүүлийн зоосыг заавал шалгана.

x бүрт n зоос туршина: хугацаа O(n · s), санах ой O(s). n = 100, s = 1 000 000 бол 100 сая алхам, ойролцоогоор нэг секунд.

Түгээмэл алдаа

  • dp[0] = 0-ийг мартах. Тэгвэл ямар ч мөнгө бүрдэхгүй.
  • INF-ийг INT_MAX гэж авах. Тэгвэл dp[x - c[i]] + 1 overflow болж сөрөг тоо гарна. Энэ кодод INF = 1e9 тул 1e9 + 1 нь int-д багтаад min-д зүгээр л ялагдана.
  • c[i] <= x шалгалтыг мартвал сөрөг index уншина.
  • Хариу INF хэвээр байхад -1 биш INF-ийг хэвлэх.

Хязгаарын тохиолдол

  • Бүрдэхгүй мөнгө: 4, 6 зоосоор 9 төгрөг. dp[9] = INF хэвээр тул -1.
  • 1 төгрөгийн зоос байвал ямар ч мөнгө заавал бүрдэнэ.
  • Зоос нь s-ээс их: c[i] <= x хэзээ ч биелэхгүй, тэр зоос огт оролцохгүй.

Өөрийгөө шалга

  1. 1, 3, 4 зоосоор 7 төгрөгийг хамгийн цөөндөө хэдэн зоосоор бүрдүүлэх вэ?

    Хариу харах

    2: 3 + 4.

  2. Ганц 2 төгрөгийн зоостой бол 3 төгрөгт хариу хэд вэ?

    Хариу харах

    -1. Тэгш биш мөнгө бүрдэхгүй.

  3. 1, 5, 6 зоосоор 10 төгрөг бүрдүүлэхэд Greedy хэдэн зоос авах вэ? Зөв хариу хэд вэ?

    Хариу харах

    Greedy 6 + 1 + 1 + 1 + 1, таван зоос авна. Зөв хариу 2: 5 + 5.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.1, 3, 4 зоос, s = 6 үед dp[0]-ээс dp[6] хүртэл бөглө.

    Hint харах

    x бүрт гурван зоосыг сүүлийн зоос болгож туршаад хамгийн багыг ав.

    Хариу ба тайлбар

    0, 1, 2, 1, 1, 2, 2. Хариу dp[6] = 2.

  2. 2.Хамгийн цөөн зоос биш, бүрдүүлэх аргын тоог ол. Зоосны дараалал хамаагүй: 3 + 1 ба 1 + 3 нэг арга.

    Hint харах

    Гадна loop-ыг зоосоор, дотор loop-ыг мөнгөөр явуулбал дарааллыг давхар тоолохгүй. dp[0] = 1.

    Хариу ба тайлбар

    for (c : coins) for (x = c; x <= s; x++) dp[x] += dp[x - c]; 1, 3, 4 зоос, s = 6 бол 4 арга: 1+1+1+1+1+1, 1+1+1+3, 1+1+4, 3+3.

  3. 3.Хариуд ямар зоосууд орсныг хэвлэдэг болго.

    Hint харах

    dp[x] сайжрах бүрт ямар зоосоор сайжирсныг тусдаа array-д хадгал.

    Хариу ба тайлбар

    last[x] = c[i] гэж хадгална. Дараа нь x = s-ээс эхлээд last[x]-ийг хэвлэж, x -= last[x] хийсээр 0 хүрнэ.

Жишээ

Оролт

3 6
1 3 4

Гаралт

2

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.