დპ-ის საფუძვლები: მემოიზაცია და ცხრილი

ხუთხაზიან რეკურსიულ ფიბონაჩის n = 50-ზე წუთები სჭირდება; დაამატე ერთი მასივი და პასუხი მყისვე მოდის. ეს ერთი ხრიკი, ქვეამოცანების პასუხების დამახსოვრება, არის დინამიური პროგრამირება და ის ინტერვიუებისა და ოლიმპიადების ამოცანების დიდ ნაწილს ხსნის.

საშუალო⏱ 14 წთ

←ეყრდნობა

4ქვესიმრავლეებისა და გადანაცვლებების გენერაციადპ არის სრული გადარჩევა პლუს მეხსიერება.0რეკურსია და გამოძახებათა სტეკიმემოიზაცია რეკურსიული ფუნქციაა, რომელიც თავის პასუხებს იწერს.6ციკლები, ტოპოლოგიური სორტირება, ორწილადობადპ-ის მდგომარეობები აციკლურ გრაფს ქმნის და ცხრილი ტოპოლოგიური რიგით უნდა შეივსოს.

გზას უხსნის→

10ერთგანზომილებიანი დპ: მონეტები და LISერთგანზომილებიანი დპ მემოს ცხრილური ფორმაა ერთი ინდექსით, მარცხნიდან მარჯვნივ.10ფლოიდ-ვორშელი: დპ გრაფზემდგომარეობაა „უმოკლესი გზა მხოლოდ პირველი k წვეროს გამოყენებით“: კლასიკური დპ.10დპ ხეებზეხეზე დპ იგივე მემოს იდეაა, თითო მდგომარეობით ყოველ წვეროზე.10ბიტმასკური დპქვესიმრავლეებზე მემოიზაცია n! მარშრუტს 2ⁿ·n მდგომარეობად აქცევს.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ერთი და იგივე კითხვა, ისევ და ისევ

დავწეროთ ფიბონაჩი ყველაზე პირდაპირი გზით: fib(n) = fib(n-1) + fib(n-2), სადაც fib(0) = 0, fib(1) = 1. კოდი სწორია, მაგრამ საშინლად ნელია.

დავხატოთ fib(5)-ის გამოძახებები და მიზეზი მაშინვე ჩანს: fib(3) ორჯერ ითვლება, fib(2) სამჯერ, და ყოველი გამეორება თან მთელ თავის ქვეხეს მოათრევს. გამოძახებების რაოდენობა φⁿ ≈ 1.6ⁿ-ის მსგავსად იზრდება, ამიტომ fib(50) ათობით მილიარდ გამოძახებას აკეთებს.

ამასთან, განსხვავებული კითხვა მხოლოდ n + 1 არის: fib(0), fib(1), …, fib(n). რეკურსია რთულ საქმეს კი არ აკეთებს, ის ერთსა და იმავეს იმეორებს. ამას ქვეამოცანების გადაფარვა ჰქვია და ეს პირველი ნიშანია, რომ დინამიური პროგრამირება (დპ) დაგვეხმარება.

ფერადი წვეროები გამეორებებია: ერთი და იგივე ქვეამოცანა თავიდან იხსნება.

02დამახსოვრების ორი გზა: მემო და ცხრილი

ზემოდან ქვემოთ (მემოიზაცია). რეკურსიას ვტოვებთ და ვამატებთ დამახსოვრებას. fib(k)-ის გამოთვლამდე ვამოწმებთ memo[k]-ს; თუ პასუხი იქ არის, ვაბრუნებთ. თუ არა, ვითვლით, ვინახავთ და ვაბრუნებთ. ყოველი ქვეამოცანა ერთხელ იხსნება: fib(5) 15-ის ნაცვლად 9 გამოძახებას აკეთებს, fib(50) კი მილიარდების ნაცვლად 99-ს.

ქვემოდან ზემოთ (ტაბულაცია). რეკურსიას საერთოდ ვტოვებთ. მასივს ვავსებთ უმცირესი ქვეამოცანიდან: f[0] = 0, f[1] = 1, შემდეგ f[i] = f[i-1] + f[i-2], i = 2..n. არც სტეკი, არც ძებნა ქეშში, მხოლოდ ციკლი.

ორივე O(n) დროს იძლევა. მემოიზაცია უფრო მარტივი პირველი ნაბიჯია (მომუშავე კოდს მხოლოდ ქეშს ვუმატებთ) და მხოლოდ საჭირო მდგომარეობებს ითვლის. ტაბულაცია პრაქტიკაში უფრო სწრაფია, სტეკს ვერ გადაავსებს და ხშირად საშუალებას გვაძლევს მხოლოდ ბოლო სტრიქონი შევინახოთ, აქ სულ ორი ცვლადი.

03როდის მუშაობს დპ: ორი თვისება

დპ გამოიყენება, როცა ამოცანას ორივე თვისება აქვს:

ქვეამოცანების გადაფარვა: რეკურსია ერთსა და იმავე პატარა კითხვებს ხვდება. (შერწყმით სორტირება მასივს *სხვადასხვა* ნახევრებად ყოფს, ამიტომ დამახსოვრება მას არ შველის.)
ოპტიმალურობის თვისება ქვეამოცანებისთვის: დიდი ამოცანის საუკეთესო პასუხი პატარების საუკეთესო პასუხებისგან იგება. A-დან C-მდე B-ზე გამავალი უმოკლესი გზა შეიცავს A-დან B-მდე უმოკლეს გზას.

სასარგებლო სურათი: ყოველი ქვეამოცანა დავხატოთ წვეროდ, ხოლო u → v წიბო გავავლოთ, თუ v-ს u-ს პასუხი სჭირდება. ფიბონაჩისთვის 15 გამოძახების ხის ნაცვლად ვიღებთ 6 წვეროს ერთ ხაზზე, ერთი და ორი ნაბიჯის ნახტომებით. ამ გრაფში ციკლი არასდროს არის (ქვეამოცანა საკუთარ თავზე ვერ იქნება დამოკიდებული), ანუ ის აციკლური ორიენტირებული გრაფია, და ქვეამოცანების ტოპოლოგიური რიგით ამოხსნა ზუსტად ისაა, რასაც ქვემოდან ზემოთ ციკლი აკეთებს.

04ყოველი დპ არის უმოკლესი გზა აციკლურ გრაფზე

ეს სურათი სერიოზულად მივიღოთ. წონად აციკლურ გრაფში წვერომდე უმოკლესი მანძილია

dist[v] = min(dist[u] + w(u, v)) ყველა u → v წიბოზე,

და მისი გამოთვლა ერთი გავლით შეიძლება, თუ წვეროებს ტოპოლოგიური რიგით ვამუშავებთ: როცა v-ს მივადგებით, ყველა u, რომელიც v-ზე მიუთითებს, უკვე საბოლოოა. არც პრიორიტეტული რიგი, არც განმეორებითი რელაქსაცია, მხოლოდ O(V + E).

ახლა ნებისმიერი დპ-ის რეკურენტული თანაფარდობა ამ ენაზე წავიკითხოთ. მდგომარეობები წვეროებია, არჩევანი წიბოებია, არჩევანის ფასი წიბოს წონაა, min ან max საუკეთესო შემავალ წიბოს ირჩევს, საბაზისო შემთხვევა კი საწყისი წვეროა. მონეტები, ზურგჩანთა, უსქ და გზები ბადეში, რომლებსაც შემდეგ გაკვეთილებში ნახავ, ერთი და იგივე იდეაა სხვადასხვა გრაფზე. დპ-ის აგებისას იკითხე: რა არის ჩემი წვეროები და რა რიგით შემიძლია მათი დასრულება?

მარცხნიდან მარჯვნივ: ყოველი წვერო მხოლოდ შემავალ წიბოებს უყურებს.

05სრული გადარჩევიდან დპ-მდე: რეცეპტი

სრული გადარჩევის ეტაპზე წერდი რეკურსიულ ფუნქციებს, რომლებიც ყველა არჩევანს ცდიან. დპ ხშირად ზუსტად იგივე კოდია, პლუს მემო. თუ რეკურსიული ფუნქციის შედეგი მხოლოდ მის არგუმენტებზეა დამოკიდებული (და არა გზაში შეცვლილ გლობალურ მდგომარეობაზე), ეს არგუმენტები მდგომარეობაა და პასუხი მათით შეგვიძლია დავიმახსოვროთ.

რეცეპტი:

მდგომარეობა: რას ნიშნავს dp[...], ერთი წინადადებით? (fib(i) = i-ური ფიბონაჩის რიცხვი.)
გადასვლა: როგორ იგება მდგომარეობა პატარებისგან?
ბაზა: მდგომარეობები, რომლებიც ფიქრის გარეშე ვიცით.
რიგი: ვავსებთ ისე, რომ დამოკიდებულებები წინ იყოს, ან ამას მემოიზებული რეკურსიას ვანდობთ.
პასუხი: რომელი მდგომარეობა, ან მდგომარეობების რომელი min/max არის საბოლოო შედეგი?

სირთულე = (მდგომარეობების რაოდენობა) × (სამუშაო თითო მდგომარეობაზე). დპ-ის შეცდომების უმეტესობა ბუნდოვანი მდგომარეობიდან მოდის, ამიტომ ის წინადადება პირველ რიგში დაწერე.

ფასი ერთი შეხედვით

გულუბრყვილო რეკურსიული fib(n)O(φⁿ)

მემოიზებული ან ცხრილით fib(n)O(n)

მეხსიერება, თუ მხოლოდ ბოლო ორ მნიშვნელობას ვინახავთO(1)

ნებისმიერი დპstates × work per state

დაიმახსოვრე

დპ მაშინ ამართლებს, როცა ქვეამოცანები ერთმანეთს ფარავს და ოპტიმალური პასუხი ოპტიმალური ქვეპასუხებისგან იგება.
მემოიზაცია რეკურსიას ქეშს უმატებს; ტაბულაცია ცხრილს ქვემოდან ზემოთ, დამოკიდებულებების რიგით ავსებს; ორივეს სირთულეა მდგომარეობები × სამუშაო თითოზე.
მდგომარეობები აციკლური გრაფის წვეროებად წარმოიდგინე: დპ-ის თანაფარდობა ტოპოლოგიური რიგით გამოთვლილი უმოკლესი (ან უგრძესი) გზაა.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: უყურე გამოძახებების მთვლელს: გულუბრყვილო ხე 15 გამოძახებას აკეთებს, მემოიზაცია მთელ გაფერმკრთალებულ ქვეხეებს ტოვებს, ცხრილი კი 4 შეკრებით ივსება. სცადე n = 7.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

გულუბრყვილო რეკურსია: fib(5) · გამოძახებები: 1

გამოძახება fib(5). (გამოძახება #1)

ფსევდოკოდი

 1 fib(n): if n < 2 return n 2 naive:  return fib(n-1) + fib(n-2)   // recomputes subproblems 3 memoized: if cached return it; else compute, cache, return 4 tabulation: table[0]=0, table[1]=1, 5   table[i] = table[i-1] + table[i-2]   // bottom-up

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

მემოიზაციით fib(30)-ის გამოთვლისას რამდენჯერ ითვლება რეალურად (და არა მხოლოდ მოიძებნება) fib(k)-ს სხეული?

№2

რომელ ამოცანას არ შველის მემოიზაცია?

№3

დპ-ს აქვს dp[i][j] მდგომარეობები, 0 ≤ i, j ≤ n, და თითოეული n ვარიანტის min-ს იღებს. რა არის მუშაობის დრო?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeFibonacci Number დამწყები↗LeetCodeClimbing Stairs დამწყები↗CSESDice Combinations საშუალო↗LeetCodeHouse Robber საშუალო↗CSESRemoving Digits საშუალო↗