დპ ბადეზე

რამდენი გზით შეიძლება ბადის ზედა მარცხენა კუთხიდან ქვედა მარჯვენამდე მისვლა, თუ მხოლოდ მარჯვნივ ან ქვევით ვმოძრაობთ?

(i, j) უჯრაში შემავალი ყოველი გზა ან ზემოდან მოდის, ან მარცხნიდან, და ეს ორი ჯგუფი არ იკვეთება. ამიტომ

ways[i][j] = ways[i−1][j] + ways[i][j−1]

ზედა სტრიქონსა და მარცხენა სვეტს თითო გზა აქვს (სწორი ხაზი): ესაა საბაზისო შემთხვევები. ვავსებთ სტრიქონ-სტრიქონ, მარცხნიდან მარჯვნივ, და ორივე მეზობელი ყოველთვის მზადაა.

4 × 5 ბადეზე კუთხეში 35 გამოდის. შეიძლება პასკალის სამკუთხედი იცანი: პასუხი ბინომიალური კოეფიციენტია C(m+n−2, m−1). მაგრამ ამოცანის შეცვლისას, მაგალითად როცა ზოგი უჯრა დაბლოკილია, მხოლოდ დპ გადარჩება.

ნამდვილ ბადეებს კედლები აქვს. დაბლოკილი უჯრა უბრალოდ იღებს ways = 0-ს (ან dp = ∞-ს ღირებულებების შემთხვევაში), და იგივე წესი მის გარშემო გრძელდება. ყურადღება მიაქციე საბაზისო შემთხვევებს: კედელი პირველ სტრიქონში მის მარჯვნივ ყველა უჯრას ბლოკავს.

მთელი ცხრილი იშვიათად გჭირდება. i-ური სტრიქონი მხოლოდ i−1-ე სტრიქონს და მარცხენა უჯრას კითხულობს, ამიტომ C სიგრძის ერთი მასივი საკმარისია: დასათვლელად row[j] += row[j−1], ღირებულებებისთვის row[j] = grid + min(row[j], row[j−1]). მეხსიერება O(R·C)-დან O(C)-მდე მცირდება.

„ორგანზომილებიანი ცხრილი, სადაც ყოველი უჯრა ზედა, მარცხენა ან დიაგონალური მეზობლიდან ითვლება“ დპ-ის ყველაზე გავრცელებული ფორმაა. მას ზურგჩანთაში, უსქ-სა და რედაქტირების მანძილში შეხვდები; იცვლება მხოლოდ უჯრების მნიშვნელობა და გაერთიანების წესი.