ერთგანზომილებიანი დპ: მონეტები და LIS

ხურდის დაბრუნება, დაგეგმვა, აქციების ფასები, ტექსტის განლაგება: ბევრი ამოცანა ერთ მასივამდე დადის, სადაც ყოველი უჯრა „საუკეთესო პასუხია პრეფიქსის ან თანხისთვის“. აქ ორ კლასიკურ ფორმას ისწავლი და ათობით სხვას იცნობ.

საშუალო⏱ 14 წთ

←ეყრდნობა

10დპ-ის საფუძვლები: მემოიზაცია და ცხრილიერთგანზომილებიანი დპ მემოს ცხრილური ფორმაა ერთი ინდექსით, მარცხნიდან მარჯვნივ.7ხარბი იდეა და როდის ცდებამონეტების ამოცანაში ხარბი ცდებოდა; დპ ყველა მონეტას ცდის და სწორ პასუხს იძლევა.5დაბალანსებული ხეები და set / mapO(n log n) LIS საუკეთესო ბოლოებს დალაგებულად ინახავს და ადგილს lower_bound-ით პოულობს, როგორც std::set-ში.

გზას უხსნის→

10დპ ბადეზებადეზე დპ ერთგანზომილებიანი დპ-ია მეორე ინდექსით: უჯრა ზედა და მარცხენა უჯრებს კითხულობს.11პრეფიქს-ფუნქცია და KMPპრეფიქს-ფუნქცია მარცხნიდან მარჯვნივ ივსება, ყოველი მნიშვნელობა წინაებიდან იგება.

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

ისწავლე

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

01სადაც ხარბი ტყდება: მონეტები {1, 3, 4}

გადავიხადოთ 6 რაც შეიძლება ნაკლები მონეტით; გვაქვს 1, 3 და 4 ნომინალის მონეტები. ხარბი იღებს უდიდეს მონეტას, რომელიც ეტევა: 4, შემდეგ 1, შემდეგ 1, სულ სამი. თუმცა 3 + 3 მხოლოდ ორი მონეტაა.

ხარბი იმიტომ ჩავარდა, რომ პირველი არჩევანი ადგილზე კარგი ჩანდა, მაგრამ დანარჩენი გააფუჭა. დპ ნაადრევად არაფერს წყვეტს: ყოველი თანხისთვის საუკეთესო პასუხს იმახსოვრებს და დიდ თანხებს მათგან აგებს.

მდგომარეობა ერთი წინადადებაა: dp[a] = მონეტების მინიმალური რაოდენობა, რომლითაც ზუსტად a თანხა შედგება. ბაზა: dp[0] = 0. ნებისმიერი სხვა a-სთვის ბოლო გამოყენებული მონეტა რაღაც c იყო, მანამდე კი a − c ოპტიმალურად შევადგინეთ. ამიტომ

dp[a] = 1 + min(dp[a − c]) ყველა c ≤ a მონეტაზე,

ხოლო dp[a] = ∞, თუ ვერცერთი მონეტა ვერ ეტევა. ვავსებთ a = 1, 2, …, A და პასუხია dp[A].

02მასივის შევსება და მონეტების აღდგენა

მონეტებისთვის {1, 3, 4} მასივი თანხებისთვის 0..6 ასეთია: 0 1 2 1 1 2 2. შევხედოთ dp[6]-ს: ის ადარებს dp[5]-ს (შემდეგ მონეტა 1), dp[3]-ს (მონეტა 3) და dp[2]-ს (მონეტა 4). უმცირესია dp[3] = 1, ამიტომ dp[6] = 2.

ცხრილი გვეუბნება, *რამდენი* მონეტაა საჭირო; *რომელი*, რომ გავიგოთ, შევსებისას გამარჯვებულ მონეტას choice[a]-ში ვინახავთ. შემდეგ უკან მივდივართ: 6-დან ვიღებთ choice[6] = 3-ს, 3-დან choice[3] = 3-ს და 0-ს ვაღწევთ. გამარჯვებული არჩევანის შენახვა და უკან სვლა ამ ეტაპის ყველა დპ-ში აღდგენის სტანდარტული ხერხია.

სირთულე: A თანხა × k მონეტა = O(A·k) დრო და O(A) მეხსიერება. ორი ხშირი ვარიაცია იმავე მასივს იყენებს:

გზების რაოდენობა A-ს გადასახდელად: min-ს ვცვლით +-ით და dp[0] = 1. როცა თანხების ციკლი გარეთაა, როგორც აქ, ითვლება დალაგებული მიმდევრობები (1+3 და 3+1 ორი გზაა); კომბინაციების დასათვლელად მონეტების ციკლი გარეთ გაიტანე, თანხების ციკლი კი შიგნით;
საერთოდ თუ შეიძლება გადახდა: ვინახავთ true/false-ს.

dp[6]-ში სამი ისარი შედის; იმარჯვებს მწვანე.

03უგრძესი ზრდადი ქვემიმდევრობა O(n²)-ში

მოცემულია 3 1 4 1 5 9 2 6; ვიპოვოთ ყველაზე გრძელი ქვემიმდევრობა (რიგი ნარჩუნდება, გამოტოვება თავისუფალია), რომელიც მკაცრად იზრდება. აქ ეს არის 3 4 5 9, სიგრძე 4.

მთავარია სწორი მდგომარეობის არჩევა. dp „პირველ i ელემენტზე“ მოუხერხებელია, რადგან მიმდევრობის გასაგრძელებლად მისი ბოლო მნიშვნელობა უნდა ვიცოდეთ. ამიტომ განვსაზღვროთ

len[i] = უგრძესი ზრდადი ქვემიმდევრობის სიგრძე, რომელიც ზუსტად i ინდექსზე მთავრდება.

მაშინ len[i] = 1 + max(len[j]) ყველა წინა j-ზე, სადაც a[j] < a[i], ან 1, თუ ასეთი არ არის. პასუხი უდიდესი len[i]-ია და არა len[n−1], რადგან საუკეთესო მიმდევრობა ნებისმიერ ადგილას შეიძლება დამთავრდეს. prev[i]-ში ვინახავთ გამარჯვებულ j-ს და საუკეთესო i-დან უკან ვბრუნდებით.

ორი ჩალაგებული ციკლი: O(n²). რამდენიმე ათასი ელემენტისთვის სავსებით საკმარისია.

04დაჩქარება ორობითი ძებნით: O(n log n)

n = 10⁵-ისთვის O(n²) ძალიან ნელია. სამაგიეროდ შევინახოთ სხვა მასივი:

tails[k] = აქამდე ნანახი k + 1 სიგრძის ზრდადი ქვემიმდევრობის უმცირესი შესაძლო ბოლო მნიშვნელობა.

პატარა ბოლო კარგია: მოგვიანებით მისი გაგრძელება უფრო ადვილია. tails ყოველთვის დალაგებულია, ამიტომ ყოველი ახალი x-ისთვის:

ორობითი ძებნით (lower_bound) ვპოულობთ პირველ ბოლოს, რომელიც ≥ x;
თუ ასეთი არ არის, x-ს ბოლოში ვამატებთ (უფრო გრძელი მიმდევრობა გაჩნდა);
წინააღმდეგ შემთხვევაში იმ ბოლოს x-ით ვცვლით (იგივე სიგრძე, უფრო პატარა ბოლო).

3 1 4 1 5 9 2 6-ზე tails საბოლოოდ არის 1 2 5 6. მისი სიგრძე, 4, არის LIS-ის სიგრძე. ფრთხილად: თავად 1 2 5 6 შეიძლება რეალური ქვემიმდევრობა არ იყოს, გარანტირებულია მხოლოდ სიგრძე. ყოველი ნაბიჯი ერთი ორობითი ძებნაა, ჯამში O(n log n). არაკლებადი მიმდევრობისთვის upper_bound გამოიყენე.

მწვანე: ბოლოში დაემატა (LIS გაიზარდა). ნარინჯისფერი: შეიცვალა უფრო პატარა ბოლოთი.

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

ხურდა, A = თანხა, k = მონეტებიO(A·k)

LIS, კლასიკური დპO(n²)

LIS, tails + ორობითი ძებნაO(n log n)

დაიმახსოვრე

1-განზომილებიან დპ-ს ერთი წინადადებით განსაზღვრული მდგომარეობა სჭირდება, მაგ. „dp[a] = მინ. მონეტები ზუსტად a-სთვის“ ან „len[i] = უგრძესი მიმდევრობა, რომელიც i-ზე მთავრდება“.
შევსებისას შეინახე გამარჯვებული არჩევანი; ამ არჩევანებით უკან სვლა რეალურ პასუხს აღადგენს.
LIS O(n²)-დან O(n log n)-მდე ჩქარდება, თუ ყოველი სიგრძისთვის უმცირეს ბოლოს ვინახავთ და მასში ორობით ვეძებთ.

ითამაშე

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

👀 რას უყურო: ჯერ უყურე, როგორ ივსება dp[a] და როგორ ბრუნდება მონეტები; შემდეგ LIS-ის ნაწილში შეადარე სვეტებზე len[] რიცხვები ქვემოთ მოცემულ ბევრად მოკლე tails[] სტრიქონს.

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

ხურდა {1,3,4}, თანხა 6 (dp[a] = მინ. მონეტები)

a	0	1	2	3	4	5	6
dp	0	∞	∞	∞	∞	∞	∞

აღდგენილი მონეტები

∅

მონეტები {1,3,4}, თანხა 6. დინამიური პროგრამირება ყოველ ქვეთანხაზე ყველა მონეტას ითვალისწინებს. dp[0] = 0.

ფსევდოკოდი

 1 coin change: dp[0]=0, dp[a]=∞ 2   for each coin c ≤ a: dp[a] = min(dp[a], dp[a-c] + 1) 3   reconstruct via stored choice[] 4 LIS: len[i] = 1 + max(len[j]) over j<i with a[j]<a[i] 5   answer = max len[i]   (tails[] + binary search: O(n log n))

1 / 1

შეამოწმე

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

№1

მონეტები {1, 5, 6, 9}, თანხა 11. რას უდრის dp[11]?

№2

რატომ არის LIS-ის პასუხი max(len[i]) და არა len[n−1]?

№3

tails = [2, 5, 7] და შემდეგი მნიშვნელობაა 6. რა ხდება?

ივარჯიშე

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

LeetCodeCoin Change საშუალო↗CSESMinimizing Coins საშუალო↗CSESCoin Combinations I საშუალო↗LeetCodeLongest Increasing Subsequence საშუალო↗CSESIncreasing Subsequence მოწინავე↗