Array-гээс зарим тоог алгасаж үүсгэх хамгийн урт өсөх дэд дарааллын (LIS) уртыг dp[i] хүснэгтээр олно.

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

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

a = [3, 1, 4, 1, 5] array-гээс зарим тоог алгасаад, үлдсэн нь хатуу өсөж байхаар сонгоё. Хамгийн урт нь хэд вэ?

3, 4, 5 эсвэл 1, 4, 5 гэвэл 3 урттай. 4 урттай өсөх дэд дараалал байхгүй. Хариу 3.

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

Энгийн арга бол бүх дэд дарааллыг үүсгэж шалгах. n тоонд 2ⁿ дэд дараалал бий, n = 40 үед л их наяд болно.

Гол санаа: дараалал хаана төгсөхийг state болгоно. dp[i] нь яг a[i]-гаар төгсөх хамгийн урт өсөх дэд дараалал. Түүний өмнөх тоо нь a[j] < a[i] байх ямар нэг j. Тиймээс dp[i] = max(dp[j] + 1). Ийм j байхгүй бол a[i] ганцаараа, урт 1.

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

дэд дараалал
Array-гээс зарим элементийг хаяж, үлдсэнийг дарааллыг нь хадгалан авсан дараалал. Зэргэлдээ байх албагүй.
dp[i]
State: a[i]-гаар төгсөх хамгийн урт өсөх дэд дарааллын урт.
i, j
i нь одоо бодож буй байрлал, j < i нь түүний өмнөх байрлал.
LIS
Longest Increasing Subsequence, хамгийн урт өсөх дэд дараалал.
a
5
0
2
1
8
2
6
3
3
4
6
5
9
6
dp
0
1
2
3
4
5
6

a = [5, 2, 8, 6, 3, 6, 9]. Зарим тоог алгасаад, үлдсэн нь өсөж байхаар сонгоё. Ийм дараалал хамгийн ихдээ хэдэн тоотой вэ? State: dp[i] нь a[i]-гаар төгсөх хамгийн урт өсөх дэд дарааллын урт.

Алхам 1 / 38
Хурд
  • i: одоо бодож буй тоо
  • j: өмнөх тоо
  • Шинэчилсэн dp[i]
  • Бодогдсон
  • Хамгийн урт өсөх дараалал
Слайд 1 / 6

Өсөх дэд дараалал

5, 2, 8, 6, 3, 6, 9. Зарим тоог алгасаад, үлдсэн нь өсөж байхаар сонгоё. Жишээ нь 2, 6, 9. Үүнээс урт нь бий юу? Бүх сонголтыг шалгавал хэтэрхий олон.

lis-dp.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[5005], dp[5005];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
cout << *max_element(dp, dp + n) << '\n';
return 0;
}

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

Өмнөх бүх state-ийн хариуг ашиглаж шинэ state-ийг боддог DP-гийн санааг сурна. HackerRank дээрх бодлогод n их тул бүх тестийг давахад O(n log n) арга хэрэгтэй.

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

1. State: dp[i] нь a[i]-гаар төгсөх хамгийн урт өсөх дэд дарааллын урт. Эхлээд бүгд 1. 2. i бүрийн хувьд түүнээс өмнөх j < i бүрийг шалгана. 3. Transition: a[j] < a[i] бол a[i]-г j дээр төгссөн дарааллын ард залгана. dp[i] = max(dp[i], dp[j] + 1). 4. Хариу нь dp-гийн хамгийн их утга. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо.

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

a[i]-гаар төгсөх хамгийн урт өсөх дарааллыг авъя. Урт нь 1-ээс их бол өмнөх тоо нь ямар нэг a[j] < a[i]. Тэр хэсэг нь a[j]-гаар төгсөх өсөх дараалал тул урт нь dp[j]-гээс хэтрэхгүй. Код бүх j-г шалгадаг тул хамгийн сайныг нь олно. Хариу нь хаана ч төгсөж болох тул dp-гийн хамгийн их утга.

Хоёр давхар loop: ойролцоогоор n² / 2 харьцуулалт, хугацаа O(n²), санах ой O(n). n = 5000 бол 12.5 сая харьцуулалт, хурдан. n = 200 000 бол O(n log n) арга хэрэгтэй.

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

  • Хариуг dp[n - 1] гэж хэвлэх. Хамгийн урт дараалал заавал сүүлийн тоогоор төгсөхгүй. *max_element(dp, dp + n) хэрэгтэй.
  • a[j] <= a[i] гэж бичих. Тэгвэл буурахгүй дараалал болж, ижил тоонууд тоологдоно.
  • dp-г 0-ээр эхлүүлэх. Тоо бүр өөрөө 1 урттай дараалал тул эхлэл 1.

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

  • n = 1: хариу 1.
  • Буурах array [5, 4, 3, 2, 1]: аль ч хоёр тоо өсөх хос үүсгэхгүй, хариу 1.
  • Бүгд ижил [2, 2, 2]: хатуу өсөх ёстой тул хариу 1.
  • Өсөх array [1, 2, 3, 4, 5]: хариу n = 5.

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

  1. [5, 2, 8, 6, 3, 6, 9]-ийн хариу хэд вэ?

    Хариу харах

    4. Жишээ нь 2, 3, 6, 9.

  2. [3, 1, 4, 1, 5]-ын dp хүснэгт ямар байх вэ?

    Хариу харах

    1, 1, 2, 1, 3.

  3. n = 1000 бол ойролцоогоор хэдэн харьцуулалт хийх вэ?

    Хариу харах

    1000 · 999 / 2 ≈ 500 000.

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

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

  1. 1.[4, 1, 3, 2, 5, 3]-ын dp хүснэгтийг бөглөөд хариуг ол.

    Hint харах

    i бүрт өмнөх бүх багаас тоог харж, хамгийн их dp дээр нь 1 нэм.

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

    dp = 1, 1, 2, 2, 3, 3. Хариу 3, жишээ нь 1, 3, 5.

  2. 2.Буурахгүй (ижил тоо зэрэгцэж болно) хамгийн урт дэд дарааллын уртыг олдог болго.

    Hint харах

    Зөвхөн нэг тэмдэг өөрчлөгдөнө.

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

    if (a[j] <= a[i]). [2, 2, 2] бол хариу 3 болно.

  3. 3.n = 200 000 үед O(n²) удаан. Хурдан арга бодож ол.

    Hint харах

    tail[k] нь k + 1 урттай өсөх дарааллын хамгийн бага сүүлийн тоо байг. Энэ array үргэлж өсөх эрэмбэтэй.

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

    Тоо бүрт lower_bound ашиглан tail дотроос түүнээс бага биш эхний элементийг олж солино, олдохгүй бол ард нь нэмнэ. tail-ийн урт нь хариу. Хугацаа O(n log n). [5, 2, 8, 6, 3, 6, 9] дээр tail = 2, 3, 6, 9.

Жишээ

Оролт

7
5 2 8 6 3 6 9

Гаралт

4

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

Бодлого

Хичээл

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