Шатаар нэг алхамдаа 1 эсвэл 2 гишгүүр өгсөж гарах аргын тоог олно. Хариу бүр өмнөх хоёр хариуны нийлбэр. DP-гийн хамгийн энгийн бодлого.

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

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

4 гишгүүртэй шат байна. Нэг алхамдаа 1 эсвэл 2 гишгүүр өгсөнө. Дээр хүртэл хэдэн янзаар гарах вэ?

Бүгдийг нь бичье: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2. Нийт 5 арга. Харин 40 гишгүүртэй бол ингэж бичиж дуусахгүй.

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

Энгийн арга бол бүх алхмын дарааллыг recursion-оор үүсгээд тоолох. Гэтэл дараалал бүрийг тусад нь үүсгэдэг тул хариу хэдэн тэрбум ч болж мэднэ, хугацаа нь хариуныхаа хэмжээгээр өснө.

Гол санаа нь сүүлийн алхам. i-р гишгүүрт хүрэхийн өмнөх алхам нь i - 1-ээс 1 гишгүүр, эсвэл i - 2-оос 2 гишгүүр байна. Өөр сонголт байхгүй. Тиймээс dp[i] = dp[i - 1] + dp[i - 2]. Жижиг хариунуудыг хүснэгтэд хадгалаад доороос дээш бөглөнө. Энэ бол DP.

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

state
Хүснэгтийн нэг нүд юуг хадгалахыг хэлнэ. Энд dp[i] нь i-р гишгүүрт хүрэх аргын тоо.
transition
Нэг state-ийг өмнөх state-үүдээс бодох томьёо: dp[i] = dp[i - 1] + dp[i - 2].
base case
Томьёогүйгээр шууд мэдэх эхний утгууд: dp[0] = dp[1] = 1.
long long
64 битийн бүхэл тоо. Хариу хурдан томордог тул int хүрэлцэхгүй.
dp
0
1
2
3
4
5
6
7

7 гишгүүртэй шат байна. Нэг алхамдаа 1 эсвэл 2 гишгүүр өгсөнө. Хамгийн дээд гишгүүрт хэдэн янзаар хүрэх вэ? State: dp[i] нь i-р гишгүүрт хүрэх аргын тоо.

Алхам 1 / 9
Хурд
  • Бөглөж буй dp[i]
  • Нэмж буй хоёр утга
  • Бөглөсөн
  • Хариу
Слайд 1 / 6

Шатаар өгсөх

7 гишгүүртэй шат байна. Нэг алхамдаа 1 эсвэл 2 гишгүүр өгсөнө. Дээр хүртэл хэдэн янзаар гарах вэ? Бүх замыг нэг нэгээр нь тоолбол их удна. Илүү ухаалаг арга бий.

climbing-stairs.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[95];
int main() {
cin >> n;
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << dp[n] << '\n';
return 0;
}

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

DP буюу Dynamic Programming-ийн гол санааг ойлгоно: том бодлогын хариуг жижиг бодлогуудын хариунаас бүтээж, хүснэгтэд хадгална. Жижиг бодлого бүрийг state, тэдгээрийг холбох томьёог transition гэдэг. HackerRank дээрх "Davis' Staircase" бодлого нь 1, 2, 3 гишгүүрээр алхдаг хувилбар.

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

1. State: dp[i] нь i-р гишгүүрт хүрэх аргын тоо. 2. Base case: dp[0] = dp[1] = 1. Доор зогсох ганц арга бий, 1-р гишгүүрт ч ганц арга бий. 3. Transition: i-р гишгүүрт сүүлийн алхмаараа 1 эсвэл 2 гишгүүр өгсөж ирнэ. Тиймээс dp[i] = dp[i − 1] + dp[i − 2]. 4. Хариу нь dp[n]. Оролт: гишгүүрийн тоо n (n ≤ 90).

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

i-р гишгүүрт хүрэх арга бүр сүүлийн алхмаараа хоёр бүлэгт хуваагдана: 1 гишгүүр алхсан ба 2 гишгүүр алхсан. Хоёр бүлэг давхцахгүй, өөр бүлэг байхгүй. Эхний бүлэгт яг dp[i - 1], хоёр дахь бүлэгт яг dp[i - 2] арга бий. Иймээс нийлбэр нь зөв.

Loop n удаа эргэх тул хугацаа O(n), хүснэгтэд O(n) санах ой. n = 90 бол ердөө 89 нэмэх үйлдэл. Шууд recursion бол n = 40 үед л 300 сая гаруй дуудлага хийнэ.

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

  • int ашиглах. dp[45] = 1 836 311 903 нь int-д багтана, харин dp[46] = 2 971 215 073 багтахгүй. long long хэрэглэ.
  • dp[1] = 1-ийг мартвал dp[2] = dp[1] + dp[0] буруу гарна. Base case хоёулаа хэрэгтэй.
  • Loop-ыг i = 1-ээс эхлүүлбэл dp[-1] уншина. Loop i = 2-оос эхэлнэ.
  • Хүснэгтийн хэмжээг n-ээр яг тааруулах. dp[n] хэрэгтэй тул array дор хаяж n + 1 урттай байна.

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

  • n = 1: loop ажиллахгүй, хариу dp[1] = 1.
  • n = 2: нэг удаа нэмнэ, хариу 2 (1+1 ба 2).
  • n = 90: хариу 4 660 046 610 375 530 309, long long-д багтана.

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

  1. n = 5 бол хариу хэд вэ?

    Хариу харах

    8. Хүснэгт: 1, 1, 2, 3, 5, 8.

  2. n = 10 бол хариу хэд вэ?

    Хариу харах

    89.

  3. dp[i] бодохдоо хүснэгтийн хэдэн нүдийг уншдаг вэ?

    Хариу харах

    Хоёрыг: dp[i - 1] ба dp[i - 2].

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

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

  1. 1.n = 6 үед dp хүснэгтийг гараар бөглөөд хариуг ол.

    Hint харах

    dp[0] = dp[1] = 1-ээс эхлээд өмнөх хоёрыг нэмсээр яв.

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

    1, 1, 2, 3, 5, 8, 13. Хариу 13.

  2. 2.Нэг алхамдаа 1, 2 эсвэл 3 гишгүүр өгсөж болдог бол кодыг өөрчил.

    Hint харах

    Сүүлийн алхам одоо гурван янз байна. i - 3 сөрөг болохоос сэргийл.

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

    dp[i] = dp[i - 1] + dp[i - 2] + (i >= 3 ? dp[i - 3] : 0). n = 4 бол хүснэгт 1, 1, 2, 4, 7, хариу 7.

  3. 3.Зарим гишгүүр эвдэрсэн, түүн дээр гишгэж болохгүй. n = 5, 3-р гишгүүр эвдэрсэн бол хэдэн арга байх вэ?

    Hint харах

    Эвдэрсэн гишгүүрт хүрэх аргын тоог юу гэж тавих вэ?

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

    Эвдэрсэн i-д dp[i] = 0 гэж тавина. Хүснэгт 1, 1, 2, 0, 2, 2 болж, хариу 2.

Жишээ

Оролт

7

Гаралт

21

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

Бодлого

Хичээл

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