Ханатай торын зүүн дээд булангаас баруун доод буланд зөвхөн баруун тийш, доош алхаж очих замын тоог олно. Хоёр хэмжээст хүснэгттэй DP бодлого.

IntermediateХугацаа: O(n · m)Санах ой: O(n · m)

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

3×3 хэмжээтэй, ханагүй тор байна. Робот зүүн дээд нүднээс баруун доод нүд рүү зөвхөн баруун тийш эсвэл доош алхана. Хэдэн өөр зам байна вэ?

Хариу 6. Хэрэв голын нүд хана бол зөвхөн захаар тойрох хоёр зам үлдэнэ.

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

Энгийн арга бол бүх замыг recursion-оор нэг нэгээр нь алхаж тоолох. 5×6 ханагүй торонд ч 126 зам бий, 20×20 торонд хэдэн арван тэрбум болно.

Гол санаа: нүд бүрт зөвхөн хоёр газраас орж ирнэ, дээрээс эсвэл зүүнээс. Тиймээс dp[i][j] = dp[i - 1][j] + dp[i][j - 1]. Мөр мөрөөр нь, зүүнээс баруун тийш бөглөвөл дээрх ба зүүн нүд үргэлж бэлэн байна. Хана бол 0 хэвээр үлдэнэ.

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

dp[i][j]
State: (i, j) нүдэнд хүрэх замын тоо. Мөр, багана 1-ээс эхэлнэ.
зах
Мөр 0 ба багана 0. Бүгд 0 тул эхний мөр, баганын нүдэнд тусгай нөхцөл бичих хэрэггүй.
g[i][j] == '#'
Хана. Энэ нүдийг continue хийж алгасна, dp нь 0 хэвээр.
MOD
10⁹ + 7. Хариу хэт том болдог тул үлдэгдлийг нь хадгална.
i \ j01234560
0
0
0
0
0
0
0
1
0
2
0
3
0
4
0
5
0

Робот зүүн дээд булангаас баруун доод булан руу явна. Зөвхөн баруун тийш эсвэл доош алхана. Хар нүд бол хана. Хэдэн өөр замаар хүрэх вэ? State: dp[i][j] нь (i, j) нүдэнд хүрэх замын тоо.

Алхам 1 / 27
Хурд
  • Бөглөж буй нүд
  • Transition-д уншиж буй нүд
  • Бөглөсөн
  • Хүснэгтийн зах (0)
  • Хана
  • Хариу
Слайд 1 / 6

Роботын зам

Робот зүүн дээд булангаас гараад баруун доод буланд очно. Зөвхөн баруун тийш эсвэл доош алхана. Хар нүд бол хана. Хэдэн өөр зам байна вэ?

grid-paths.cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m, dp[1005][1005];
char g[1005][1005];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) cin >> g[i][j];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '#') continue;
if (i == 1 && j == 1) {
dp[i][j] = 1;
} else {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
}
}
}
cout << dp[n][m] << '\n';
return 0;
}

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

Хоёр хэмжээст хүснэгттэй DP-гийн хамгийн энгийн жишээ: нүд бүрийн хариу нь дээд ба зүүн хөршийнхөө нийлбэр. Олимпиадад замын тоо маш их болдог тул хариуг 10⁹ + 7-д хуваасан үлдэгдлээр хэвлэдэг.

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

1. State: dp[i][j] нь (i, j) нүдэнд хүрэх замын тоо. Хүснэгтийг 0-ээр дүүрсэн зах (мөр 0, багана 0) тойрно. 2. Base case: dp[1][1] = 1. 3. Хана бол алгасна, тэнд dp = 0 хэвээр үлдэнэ. 4. Transition: бусад нүдэнд дээрээс эсвэл зүүнээс л ирнэ. dp[i][j] = dp[i − 1][j] + dp[i][j − 1]. 5. Хариу нь dp[n][m]. Оролт: эхний мөрөнд n m, дараа нь n мөр тор ("." бол зам, "#" бол хана).

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

Нүд рүү орох зам бүрийн сүүлийн алхам нь дээрээс эсвэл зүүнээс ирсэн байна. Хоёр бүлэг давхцахгүй тул нийлбэр нь яг замын тоо. Хана руу ямар ч зам орохгүй тул 0 зөв.

Нүд бүрийг нэг удаа бодно: хугацаа O(n · m), санах ой O(n · m). 1000×1000 торонд сая нүд, хором ч болохгүй.

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

  • MOD-ыг нэмсний дараа авахаа мартах. Хоёр тооны нийлбэр 2 · 10⁹-аас хэтрэхгүй тул int-д багтана, гэхдээ % MOD заавал хэрэгтэй.
  • Эхлэлийн нүдийг томьёогоор бодох. Дээр, зүүн нь хоёулаа 0 тул 0 гарна. dp[1][1] = 1-ийг тусад нь тавина.
  • Мөрийг 0-ээс уншиж, dp-г 1-ээс эхлүүлэх. Тор ба хүснэгтийн index-ийг ижил болго.
  • Эхлэл эсвэл төгсгөл хана байх. Тэгвэл хариу 0 гарах ёстой. Код эхлэл ханатай үед continue хийгээд үнэхээр 0 хэвлэнэ.

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

  • 1×m тор: ганц л зам, хариу 1 (ханагүй бол).
  • Хана замыг бүрэн хаасан: баруун доод нүд 0 хэвээр, хариу 0.
  • Ханагүй n×m тор: хариу нь C(n + m − 2, n − 1). 5×6 бол C(9, 4) = 126.

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

  1. Ханагүй 2×3 торонд хэдэн зам байх вэ?

    Хариу харах

    3.

  2. Ханагүй 5×6 торонд хэдэн зам байх вэ?

    Хариу харах

    126. Баруун тийш 5, доош 4 алхам, нийт 9 алхмаас доошлохыг 4-ийг сонгоно.

  3. Яагаад мөр 0 ба багана 0-ийг 0-ээр дүүргэдэг вэ?

    Хариу харах

    Эхний мөр, баганын нүдний дээд эсвэл зүүн хөрш нь тор дотор байхгүй. 0 байвал томьёо өөрчлөлтгүй ажилладаг.

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

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

  1. 1.3×4 тор, (2, 2) нүд хана. Хүснэгтийг гараар бөглөөд хариуг ол.

    Hint харах

    Эхний мөр бүгд 1. Ханын нүдийг 0 гэж үзээд нэм.

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

    Мөр 1: 1 1 1 1. Мөр 2: 1 # 1 2. Мөр 3: 1 1 2 4. Хариу 4.

  2. 2.Робот диагоналаар (баруун доош) ч алхаж чаддаг бол кодыг өөрчил.

    Hint харах

    Нүд рүү одоо гурван газраас орж ирнэ.

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

    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]) % MOD. Нэмэхдээ хоёр удаа MOD ав. Ханагүй 2×2 торонд 3, 3×3 торонд 13 зам.

  3. 3.Нүд бүрт зоос байна. Робот замдаа хамгийн олон зоос цуглуулахыг хүсвэл юу өөрчлөх вэ?

    Hint харах

    Замын тоо биш, хамгийн их нийлбэр хэрэгтэй. Нэмэхийн оронд юу хийх вэ?

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

    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + coin[i][j]. Хүрч болохгүй нүдийг маш бага тоогоор тэмдэглэ, тэгэхгүй бол 0 нь хүрэх замтай мэт харагдана.

Жишээ

Оролт

5 6
......
.#..#.
...#..
#.....
..#...

Гаралт

10