Greedy និង Dynamic Programming

មាតិកា

1. វិធីពីរយ៉ាងក្នុងការរចនា Algorithm
2. Greedy យកអ្វីដែលល្អបំផុតពេលនេះ
3. ឧទាហរណ៍ Greedy ការកំណត់ពេល Interval
4. នៅពេល Greedy ខុស
5. Dynamic Programming ចងចាំចម្លើយរបស់អ្នក
6. Top-Down និង Bottom-Up
7. ឡើងជណ្តើរ
8. Coin Change
9. Knapsack-Lite
10. Longest Common Subsequence
11. របៀបសម្គាល់បញ្ហា DP
12. រូបមន្ត៖ greedy.ts និង dp.ts សម្រាប់ algolab
13. សាកល្បងដោយខ្លួនឯង

1. វិធីពីរយ៉ាងក្នុងការរចនា Algorithm

ជំពូកមុនៗបានបង្រៀន structure និងបច្ចេកទេសដែលអ្នកអាចហៅឈ្មោះបាន៖ hash map, stack, binary search, BFS។ ជំពូកនេះនិយាយអំពី របៀបរចនា algorithm សម្រាប់បញ្ហាដែលសួររកចម្លើយល្អបំផុត។ "តើកាក់តិចបំផុតប៉ុន្មាន?" "តើខ្ញុំអាចចូលរួមប្រជុំបានច្រើនបំផុតប៉ុន្មាន?" "តើវិធីណាថោកបំផុត?" ទាំងនេះគឺជា optimization problem ហើយយុទ្ធសាស្ត្រពីរគ្របដណ្តប់បញ្ហាទាំងនេះបានច្រើនណាស់៖

• Greedy៖ នៅគ្រប់ជំហាន យកជម្រើសដែលមើលទៅល្អបំផុតពេលនេះ ហើយមិនមើលក្រោយវិញឡើយ។ លឿន និងសាមញ្ញ ប៉ុន្តែត្រឹមត្រូវសម្រាប់តែបញ្ហាមួយចំនួនប៉ុណ្ណោះ។
• Dynamic programming (DP)៖ បំបែកបញ្ហាទៅជាបញ្ហាតូចៗដែលត្រួតគ្នា ដោះស្រាយនីមួយៗ តែម្តង ហើយរក្សាទុកចម្លើយ។ ចំណាយពេលរចនាយូរជាង ប៉ុន្តែត្រឹមត្រូវសម្រាប់បញ្ហាច្រើនជាងឆ្ងាយ។

តើអ្នកជួបវានៅកន្លែងធ្វើការត្រង់ណា? Greedy នៅពីក្រោយការកំណត់ពេលបន្ទប់ប្រជុំ ការវេចទិន្នន័យចូល network packet តិចបំផុត និងការអាប់លុយនៅបញ្ជរគិតលុយ។ DP នៅពីក្រោយ "edit distance" ក្នុង spell-check, diff ដែលបង្ហាញអ្វីដែលផ្លាស់ប្តូររវាងឯកសារពីរ, ការគ្រោងផ្លូវ, ការរុំអត្ថបទ និងវិធីល្អបំផុតក្នុងការបែងចែកវីដេអូទៅជា chunk។ ការស្គាល់ទាំងពីរ អនុញ្ញាតឲ្យអ្នកមើលបញ្ហាមួយ ហើយជ្រើសឧបករណ៍ត្រឹមត្រូវ។

2. Greedy យកអ្វីដែលល្អបំផុតពេលនេះ

Greedy algorithm សាងសង់ចម្លើយម្តងមួយជម្រើស។ នៅគ្រប់ជំហាន វាជ្រើសជម្រើសដែល ល្អបំផុតក្នុងតំបន់ ហើយចាក់សោវា។ វាមិនពិចារណាឡើងវិញទេ។

ឧទាហរណ៍ប្រចាំថ្ងៃ៖ អ្នកជំពាក់នរណាម្នាក់ 63 សេន ហើយមានកាក់តម្លៃ 25, 10, 5 និង 1។ បង់កាក់ធំបំផុតដែលនៅសល់ឲ្យសមជាបន្តបន្ទាប់៖

function greedyCoins(coins: number[], amount: number): number[] {
  const sorted = [...coins].sort((a, b) => b - a); // biggest first
  const used: number[] = [];
  let left = amount;
  for (const c of sorted) {
    while (left >= c) {
      used.push(c);
      left -= c;
    }
  }
  return left === 0 ? used : [];
}

console.log(greedyCoins([25, 10, 5, 1], 63));
// [ 25, 25, 10, 1, 1, 1 ]

កាក់ប្រាំមួយ ហើយនោះពិតជាតិចបំផុតសម្រាប់តម្លៃកាក់ទាំងនេះ។ Greedy គួរឲ្យទាក់ទាញ ព្រោះវាជាធម្មតាខ្លី និងលឿន៖ sort ម្តង រួច loop ម្តង។ ថ្លៃចំណាយគឺ O(n log n) សម្រាប់ sort និង O(n) សម្រាប់ loop។

រាល់ greedy algorithm ពឹងលើការអះអាងមួយដែលអាចបញ្ជាក់បាន៖ ការជ្រើសជម្រើសល្អបំផុតក្នុងតំបន់ មិនអាចរារាំងយើងពីការទទួលបានចម្លើយល្អបំផុតរួមបានឡើយ។ ពេលខ្លះការអះអាងនេះពិត (ដូចកាក់ទាំងនេះ)។ ពេលខ្លះវាមិនពិត។ ផ្នែកទី 4 បង្ហាញថាវាមើលទៅដូចម្តេច ដើម្បីកុំឲ្យអ្នកជឿ greedy បិទភ្នែក។

3. ឧទាហរណ៍ Greedy ការកំណត់ពេល Interval

នេះគឺជាបញ្ហាមួយដែល greedy ជាចម្លើយត្រឹមត្រូវ ហើយការជ្រើស "ល្អបំផុត" មិនច្បាស់លាស់ទេ។

អ្នកមានបន្ទប់ប្រជុំមួយ និងបញ្ជីសំណើប្រជុំ ដែលនីមួយៗមានម៉ោងចាប់ផ្តើម និងម៉ោងបញ្ចប់។ ជ្រើស ចំនួនប្រជុំច្រើនបំផុត ដែលមិនត្រួតគ្នា។

តើគួរយកការប្រជុំមួយណាមុន? មានគំនិតបីដែលគួរឲ្យល្បួង៖

• មួយដែល ចាប់ផ្តើមមុនគេ។ មិនល្អ៖ ការប្រជុំពី 0 ដល់ 100 នឹងរារាំងអ្វីៗទាំងអស់។
• មួយ ខ្លីបំផុត។ មិនល្អ៖ ការប្រជុំតូចមួយនៅកណ្តាល អាចរារាំងការប្រជុំវែងពីរនៅសងខាង។
• មួយដែល បញ្ចប់មុនគេ។ នេះទុកកន្លែងទំនេរច្រើនបំផុតសម្រាប់ការប្រជុំផ្សេងទៀត។

គំនិតទីបីគឺត្រឹមត្រូវ ហើយអាចបញ្ជាក់បាន៖ ការប្រជុំដែលបញ្ចប់មុនគេ ទុកពេលទំនេរយ៉ាងហោចណាស់ស្មើនឹងជម្រើសផ្សេងណាមួយ។ ដូច្នេះ៖

1. Sort តាមម៉ោង បញ្ចប់។
2. យកការប្រជុំមួយ ប្រសិនបើវាចាប់ផ្តើមនៅ ឬក្រោយម៉ោងបញ្ចប់នៃការប្រជុំចុងក្រោយដែលបានជ្រើស។

interface Interval {
  start: number;
  end: number;
}

function maxNonOverlapping(intervals: Interval[]): Interval[] {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const chosen: Interval[] = [];
  let lastEnd = -Infinity;

  for (const iv of sorted) {
    if (iv.start >= lastEnd) {
      chosen.push(iv);
      lastEnd = iv.end;
    }
  }
  return chosen;
}

const meetings = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 3, end: 9 },
  { start: 5, end: 9 },
  { start: 6, end: 10 },
  { start: 8, end: 11 },
];

console.log(maxNonOverlapping(meetings).map((m) => `${m.start}-${m.end}`));
// [ '1-4', '5-7', '8-11' ]

ដើរតាមជំហាន។ Sort តាមម៉ោងបញ្ចប់៖ 1-4, 3-5, 0-6, 5-7, 3-9, 5-9, 6-10, 8-11។ យក 1-4 (ម៉ោងបញ្ចប់ចុងក្រោយ 4)។ 3-5 ចាប់ផ្តើមនៅ 3 មុន 4 ដូច្នេះរំលង។ 0-6 រំលង។ 5-7 ចាប់ផ្តើមនៅ 5 ដែលនៅ ឬក្រោយ 4៖ យកវា (ម៉ោងបញ្ចប់ចុងក្រោយ 7)។ 3-9, 5-9 និង 6-10 ទាំងអស់ចាប់ផ្តើមមុន 7៖ រំលង។ 8-11 ចាប់ផ្តើមនៅ 8៖ យក។ ការប្រជុំបីដង ហើយមិនមានចម្លើយណាល្អជាងនេះទេ។

លំនាំដូចគ្នានេះដោះស្រាយ "ចំនួនព្រួញតិចបំផុតដើម្បីបំផ្ទុះបាឡុង", "ចំនួនបន្ទប់ប្រជុំតិចបំផុត" (ដោយប្រើ heap, ជំពូកទី 10) និង "លុប interval តិចបំផុត ដើម្បីឲ្យដែលនៅសល់មិនត្រួតគ្នា"។ ពេលអ្នកឃើញ interval ចូរគិតមុនថា "sort តាមម៉ោងបញ្ចប់" ឬ "sort តាមម៉ោងចាប់ផ្តើម"។

4. នៅពេល Greedy ខុស

ត្រឡប់ទៅកាក់វិញ។ ឧបមាថាប្រទេសចម្លែកមួយមានកាក់តម្លៃ 4, 3 និង 1 ហើយអ្នកត្រូវបង់ 6។ Greedy យកកាក់ធំបំផុតមុន៖

console.log(greedyCoins([4, 3, 1], 6));
// [ 4, 1, 1 ]   three coins

ប៉ុន្តែ 3 + 3 គឺមានតែកាក់ពីរប៉ុណ្ណោះ។ Greedy បានប្តូរចិត្តទៅលើ 4 ហើយមិនអាចយកវាត្រឡប់វិញបានទេ។ ករណីមួយទៀត៖ កាក់ 5 និង 2 ត្រូវបង់ 3។ Greedy សាកល្បង 5 (ធំពេក) សាកល្បង 2 រួចនៅសល់ 1 ហើយគ្មានកាក់សម្រាប់វាទេ ដូច្នេះវាត្រឡប់ [] (បរាជ័យ)។ តាមពិត 3 មិនអាចបង់បានទាល់តែសោះជាមួយកាក់ទាំងនេះ។ ករណីទីមួយគឺជាគ្រោះថ្នាក់ពិតប្រាកដ៖ greedy ផ្តល់ចម្លើយ ហើយចម្លើយនោះខុស ដោយគ្មាន error ណាមួយព្រមានអ្នកឡើយ។

រូបិយប័ណ្ណពិតត្រូវបានរចនាឡើងដើម្បីឲ្យ greedy ដំណើរការ។ ប៉ុន្តែសំណុំកាក់តាមអំពើចិត្តមិនមែនទេ។ ដូច្នេះតើអ្នកសម្រេចយ៉ាងដូចម្តេចថា greedy មានសុវត្ថិភាព?

• ព្យាយាម បញ្ជាក់ ការអះអាងថា "ជម្រើសល្អបំផុតមិនរារាំងចម្លើយល្អបំផុត" ឬរក counterexample លើ input តូចមួយ។ ពីរនាទីជាមួយខ្មៅដៃ និងឧទាហរណ៍ពិបាកមួយ ជួយសន្សំម៉ោងនៃការ debug។
• Greedy មានទំនោរដំណើរការ នៅពេលដែល sort ផ្តល់លំដាប់ច្បាស់លាស់នៃ "ល្អបំផុត" ហើយការយកវាមិនប៉ះពាល់ពេលក្រោយ (interval តាមម៉ោងបញ្ចប់)។
• Greedy មានទំនោរបរាជ័យ នៅពេលដែលជម្រើស ធ្វើអន្តរកម្មគ្នា៖ ការយកអ្វីមួយផ្លាស់ប្តូរតម្លៃនៃអ្វីផ្សេងទៀត (កាក់, ការវេចកាបូប)។

នៅពេល greedy បរាជ័យ អ្នកត្រូវសាកល្បងជម្រើសផ្សេងៗ ហើយនោះគឺជាទ្វារទៅកាន់ dynamic programming។

5. Dynamic Programming ចងចាំចម្លើយរបស់អ្នក

អ្នកបានជួបគំនិតស្នូលនៅក្នុងជំពូក recursion ក្នុងសំលៀកបំពាក់ផ្សេង៖ memoization។ Dynamic programming គឺ recursion បូកនឹងការចងចាំ ដែលប្រើនៅពេលបញ្ហាតូចដដែលលេចឡើងម្តងហើយម្តងទៀត។

រំលឹក Fibonacci។ លេខនីមួយៗគឺជាផលបូកនៃលេខពីរមុនវា៖

function fibSlow(n: number): number {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

វាត្រឹមត្រូវ និងខ្លី ប៉ុន្តែយឺត។ fib(5) ហៅ fib(4) និង fib(3)។ ប៉ុន្តែ fib(4) ក៏ហៅ fib(3) ដែរ។ ការងារដដែលត្រូវបានធ្វើម្តងទៀត៖

                fib(5)
              /        \
          fib(4)       fib(3)        <- fib(3) is computed twice
         /     \       /    \
     fib(3)  fib(2) fib(2) fib(1)    <- fib(2) three times in total

ចំនួនការហៅកើនឡើងប្រហែល 1.6 ដងរាល់ពេល n កើនមួយ។ ការរាប់ការហៅពិត៖

នោះគឺជាកំណើន O(2^n)។ អ្នកបានឃើញរូបរាងនៃខ្សែកោងនេះក្នុងជំពូក Big-O។ fib(35) ចំណាយរួចទៅហើយរាប់សិបមិល្លីវិនាទី ហើយ fib(50) នឹងចំណាយលើសពីមួយនាទី។

គ្រឿងផ្សំពីរប្រាប់អ្នកថា DP អាចធ្វើបាន៖

1. Overlapping subproblems៖ បញ្ហាតូចដដែលត្រូវការច្រើនដង (fib(3) ខាងលើ)។ ប្រសិនបើគ្រប់ subproblem ខុសគ្នា នោះគ្មានអ្វីត្រូវប្រើឡើងវិញទេ។ នោះគឺជា divide and conquer ធម្មតា ដូច merge sort។
2. Optimal substructure៖ ចម្លើយល្អបំផុតនៃបញ្ហាធំ ត្រូវបានសាងសង់ពីចម្លើយល្អបំផុតនៃបញ្ហាតូចៗ។

6. Top-Down និង Bottom-Up

មានវិធីពីរយ៉ាងក្នុងការសរសេរដំណោះស្រាយ DP។ ទាំងពីរធ្វើការងារដូចគ្នា ជាមួយ Big-O ដូចគ្នា។

Top-down (memoization)៖ សរសេរ recursion ធម្មតា រួចបន្ថែម cache។ មុនគណនា ត្រួតពិនិត្យថាតើវាមានរួចហើយឬនៅ៖

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(10)); // 55
console.log(fibMemo(50)); // 12586269025

តម្លៃ n នីមួយៗត្រូវបានគណនាម្តង ដូច្នេះថ្លៃចំណាយធ្លាក់ពី O(2^n) មក O(n) សម្រាប់ពេលវេលា និង O(n) សម្រាប់ទំហំ (cache បូកនឹង recursion stack)។

Bottom-up (tabulation)៖ រំលង recursion។ បំពេញតារាងពី subproblem តូចបំផុតឡើងលើ ដើម្បីឲ្យអ្វីៗដែលអ្នកត្រូវការមានរួចជាស្រេច៖

function fibTable(n: number): number {
  if (n < 2) return n;
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

console.log(fibTable(50)); // 12586269025

ដោយសារតម្លៃនីមួយៗត្រូវការតែពីរមុនវា យើងមិនចាំបាច់រក្សាតារាងទាំងមូលទេ គ្រាន់តែ variable ពីរ។ នោះធ្វើឲ្យទំហំ O(1)។ ការបង្រួមតារាងទៅត្រឹមតែក្រឡាពីរបីដែលនៅត្រូវការ គឺជាការបញ្ចប់ធម្មតានៃ DP។

កំណត់សម្គាល់អំពីលេខ៖ fib(78) គឺជាលេខ Fibonacci ចុងក្រោយដែល number របស់ JavaScript រក្សាបានយ៉ាងត្រឹមត្រូវ។ ក្រោយពីនោះ លទ្ធផលបាត់បង់ភាពជាក់លាក់ដោយស្ងាត់ៗ (ដែនកំណត់ integer ពីស៊េរី Math)។ ប្រើ BigInt ប្រសិនបើអ្នកត្រូវការ fib(100)។

រូបមន្តជាក់ស្តែងសម្រាប់បញ្ហា DP ណាមួយ មិនថាអ្នកជ្រើសរចនាប័ទ្មណា៖

1. កំណត់ state៖ តើ input នៃ subproblem មានន័យយ៉ាងណា? ("dp[i] គឺជាចំនួនកាក់តិចបំផុតដើម្បីបង្កើតចំនួន i។")
2. សរសេរ recurrence៖ តើ state មួយពឹងលើ state តូចជាងយ៉ាងដូចម្តេច?
3. កំណត់ base case៖ state តូចបំផុតដែលអ្នកដឹងដោយផ្ទាល់។
4. សម្រេច លំដាប់៖ state ណាត្រូវតែរួចរាល់មុន state ផ្សេង។
5. អាន ចម្លើយ៖ state ណាគឺជាចម្លើយចុងក្រោយ?

7. ឡើងជណ្តើរ

បញ្ហា DP ដំបូងដ៏ល្បីមួយ។ អ្នកឡើងជណ្តើរដែលមាន n ជំហាន។ គ្រប់ការផ្លាស់ទី អ្នកដើរ 1 ឬ 2 ជំហាន។ តើមានប៉ុន្មានវិធីខុសគ្នាដើម្បីឡើងដល់កំពូល?

ដើរតាមរូបមន្ត។ ឲ្យ ways(n) ជាចំនួនវិធីដើម្បីឡើងដល់ជំហាន n។ អ្នកមកដល់ជំហាន n ពីជំហាន n - 1 (ដោយការដើរ 1 ជំហាន) ឬពីជំហាន n - 2 (ដោយការដើរ 2 ជំហាន)។ ក្រុមផ្លូវទាំងពីរនេះមិនត្រួតគ្នាទេ ដូច្នេះ៖

ways(n) = ways(n - 1) + ways(n - 2)

ជាមួយ base case ways(0) = 1 (ឈរនៅនឹងកន្លែង៖ មួយវិធី) និង ways(1) = 1។ វាគឺជា recurrence របស់ Fibonacci ក្នុងសំលៀកបំពាក់ក្លែងក្លាយ។

function climbStairs(n: number): number {
  let a = 1; // ways(0)
  let b = 1; // ways(1)
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

console.log([1, 2, 3, 4, 5, 10].map(climbStairs));
// [ 1, 2, 3, 5, 8, 89 ]

ពិនិត្យ n = 3 ដោយដៃ៖ 1+1+1, 1+2, 2+1។ នោះគឺ 3 វិធី។ សម្រាប់ n = 4៖ 1111, 112, 121, 211, 22។ នោះគឺ 5។

នេះគឺជាមេរៀនមានប្រយោជន៍។ បញ្ហាជាច្រើនដែលមើលទៅខុសគ្នា គឺជា recurrence ដូចគ្នាក្នុងសំលៀកបំពាក់។ "តើមានប៉ុន្មានវិធីក្នុងការតម្រៀបដូមីណូលើបន្ទះ 2 x n" និង "binary string ប្រវែង n ដែលគ្មាន 1 ពីរជាប់គ្នា" មានរូបរាង Fibonacci ដូចគ្នា។ ការប្រែប្រួលមួយបន្ទាត់ទៀតគឺ "House Robber"៖ អ្នកមិនអាចប្លន់ផ្ទះជិតគ្នាពីរបានទេ ដូច្នេះសម្រាប់ផ្ទះនីមួយៗ ផលបូកល្អបំផុតគឺ ឬដោយមិនប្លន់ផ្ទះនោះ ឬផ្ទះនេះបូកនឹងផលល្អបំផុតដែលរំលងផ្ទះមុន៖

function houseRobber(nums: number[]): number {
  let take = 0; // best total if we rob the current house
  let skip = 0; // best total if we do not
  for (const n of nums) {
    [take, skip] = [skip + n, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

console.log(houseRobber([2, 7, 9, 3, 1])); // 12   (2 + 9 + 1)
console.log(houseRobber([1, 2, 3, 1]));    // 4    (1 + 3)

8. Coin Change

ឥឡូវនេះជាបញ្ហាដែល greedy បរាជ័យ។ ដោយមានតម្លៃកាក់ និងចំនួនទឹកប្រាក់ ចូររក កាក់តិចបំផុត ដែលបូកបានចំនួននោះ ឬ -1 ប្រសិនបើមិនអាចទៅរួច។

State៖ dp[a] គឺជាចំនួនកាក់តិចបំផុតដើម្បីបង្កើតចំនួន a។ Base៖ dp[0] = 0។ Recurrence៖ ដើម្បីបង្កើត a កាក់ចុងក្រោយអាចជាកាក់ណាមួយ c។ បន្ទាប់មកអ្នកត្រូវការចម្លើយល្អបំផុតសម្រាប់ a - c បូកកាក់មួយនេះ។ សាកល្បងគ្រប់កាក់ ហើយរក្សាតម្លៃតូចបំផុត៖

dp[a] = 1 + min(dp[a - c])  for every coin c with c <= a

function coinChange(coins: number[], amount: number): number {
  const dp = new Array<number>(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([4, 3, 1], 6));   // 2   (3 + 3)
console.log(coinChange([5, 2], 3));      // -1
console.log(coinChange([1, 2, 5], 11));  // 3   (5 + 5 + 1)
console.log(coinChange([2], 3));         // -1
console.log(coinChange([1], 0));         // 0

ការប្រើ Infinity ជា "មិនទាន់ទៅដល់" គឺជាល្បិចដ៏ល្អ៖ Infinity + 1 នៅតែជា Infinity ដូច្នេះ state ដែលមិនអាចទៅរួច មិនដែលឈ្នះចម្លើយពិតឡើយ។

នេះគឺជាតារាងដែលបានបំពេញសម្រាប់កាក់ [4, 3, 1] និងចំនួន 6៖

អាន dp[6]៖ សាកល្បងកាក់ 4 ដែលនៅសល់ dp[2] = 2 ដូច្នេះ 3 កាក់។ សាកល្បងកាក់ 3៖ dp[3] = 1 ដូច្នេះ 2 កាក់។ សាកល្បងកាក់ 1៖ dp[5] = 2 ដូច្នេះ 3 កាក់។ ល្អបំផុតគឺ 2។ Greedy ខកខានចំណុចនេះ ព្រោះវាមិនដែលប្រៀបធៀបជម្រើសផ្សេងៗទេ។

ថ្លៃពេលវេលាគឺ O(amount × ចំនួនកាក់) ហើយទំហំគឺ O(amount)។ នោះលឿនសូម្បីតែសម្រាប់ចំនួនធំ ចំណែកការសាកល្បងគ្រប់បន្សំគឺ exponential។

9. Knapsack-Lite

អ្នកមានកាបូបមួយដែលផ្ទុកទម្ងន់សរុប capacity។ របស់នីមួយៗមានទម្ងន់ និងតម្លៃ ហើយអ្នកអាចយករបស់នីមួយៗ យ៉ាងច្រើនម្តង។ ជ្រើសរបស់ដើម្បីបាន តម្លៃសរុបអតិបរមា។ នេះគឺជា 0/1 knapsack ដែលជាគំរូសម្រាប់ការធ្វើថវិកា ការផ្ទុកទំនិញ និងការជ្រើសថាមុខងារណាខ្លះសមក្នុង sprint មួយ។

Greedy តាម "តម្លៃល្អបំផុតក្នុងមួយទម្ងន់" អាចបរាជ័យនៅទីនេះ ដូចដែលវាបរាជ័យសម្រាប់កាក់។ យករបស់ (weight 10, value 60), (weight 20, value 100) និង (weight 30, value 120) ជាមួយ capacity 50។ សមាមាត្រគឺ 6, 5 និង 4 ដូច្នេះ greedy យកពីរដំបូង (តម្លៃ 160) ហើយទីបីលែងសមទៀត។ ប៉ុន្តែទីពីរ និងទីបីរួមគ្នាមានទម្ងន់ 50 ពិតប្រាកដ និងមានតម្លៃ 220។

State៖ dp[w] គឺជាតម្លៃល្អបំផុតដោយប្រើទម្ងន់មិនលើស w។ ដំណើរការរបស់ម្តងមួយៗ។ សម្រាប់របស់នីមួយៗ ធ្វើបច្ចុប្បន្នភាពតារាងពី capacity ធំបំផុតចុះក្រោម ដល់ទម្ងន់របស់វត្ថុ ដើម្បីឲ្យវត្ថុត្រូវបានប្រើយ៉ាងច្រើនម្តង៖

function knapsack(
  items: { weight: number; value: number }[],
  capacity: number,
): number {
  const dp = new Array<number>(capacity + 1).fill(0);

  for (const { weight, value } of items) {
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

console.log(
  knapsack(
    [
      { weight: 1, value: 15 },
      { weight: 3, value: 20 },
      { weight: 4, value: 30 },
    ],
    4,
  ),
); // 35

console.log(
  knapsack(
    [
      { weight: 10, value: 60 },
      { weight: 20, value: 100 },
      { weight: 30, value: 120 },
    ],
    50,
  ),
); // 220

ក្នុងការហៅទីមួយ ល្អបំផុតគឺរបស់ពីរដំបូង (ទម្ងន់ 1 + 3 = 4, តម្លៃ 15 + 20 = 35)។ Loop ខាងក្នុងដើរ ចុះក្រោម ដោយចេតនា។ ប្រសិនបើវាដើរឡើងលើ dp[w - weight] អាចរួមបញ្ចូលវត្ថុបច្ចុប្បន្នរួចហើយ ហើយអ្នកនឹងប្រើវាពីរដង។ នោះបំប្លែងបញ្ហាទៅជាកំណែ "របស់គ្មានដែនកំណត់"។ ទិសដៅ loop តែមួយនេះគឺជាអន្ទាក់ interview បុរាណ។

ពេលវេលា O(items × capacity), ទំហំ O(capacity)។ ប្រយ័ត្នជាមួយឈ្មោះ៖ នេះត្រូវបានហៅថា pseudo-polynomial ព្រោះវាកើនតាម តម្លៃ នៃ capacity មិនមែនតាមចំនួនខ្ទង់របស់វាទេ។

10. Longest Common Subsequence

ដោយមាន string ពីរ ចូររកប្រវែងនៃ longest common subsequence (LCS) របស់ពួកវា៖ លំដាប់តួអក្សរវែងបំផុតដែលលេចឡើងក្នុងទាំងពីរ តាមលំដាប់ដូចគ្នា ប៉ុន្តែមិនចាំបាច់នៅជាប់គ្នា។ សម្រាប់ "abcde" និង "ace" ចម្លើយគឺ 3 ("ace")។ នេះគឺជាបេះដូងនៃឧបករណ៍ diff និងការប្រៀបធៀប DNA។

បញ្ហានេះមាន input ដែលផ្លាស់ប្តូរ ពីរ ដូច្នេះ state គឺជាតារាងពីរវិមាត្រ៖ dp[i][j] គឺជាប្រវែង LCS នៃតួអក្សរ i ដំបូងនៃ a និងតួអក្សរ j ដំបូងនៃ b។

• ប្រសិនបើតួអក្សរ a[i-1] និង b[j-1] ដូចគ្នា ពួកវាពង្រីកចម្លើយល្អបំផុតសម្រាប់ prefix ខ្លីជាង៖ dp[i][j] = dp[i-1][j-1] + 1។
• ប្រសិនបើមិនដូចគ្នា ទម្លាក់តួអក្សរមួយពីម្ខាង ហើយយកលទ្ធផលល្អជាង៖ dp[i][j] = max(dp[i-1][j], dp[i][j-1])។
• Base៖ ជាមួយ string ទទេ ចម្លើយគឺ 0 ដូច្នេះជួរទី 0 និងជួរឈរទី 0 ជាសូន្យ។

function lcs(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] =
        a[i - 1] === b[j - 1]
          ? dp[i - 1][j - 1] + 1
          : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

console.log(lcs("abcde", "ace"));         // 3
console.log(lcs("abc", "def"));           // 0
console.log(lcs("AGGTAB", "GXTXAYB"));    // 4   ("GTAB")

តារាងមានទំហំ (m + 1) × (n + 1) ដូច្នេះទាំងពេលវេលា និងទំហំគឺ O(m × n)។ កំហុសទូទៅគឺការច្រឡំវិមាត្រ៖ សូមកត់សម្គាល់ថាជួរប្រើ a.length + 1 ហើយជួរឈរប្រើ b.length + 1។ មួយទៀតគឺ off-by-one៖ index i នៃតារាងសំដៅលើតួអក្សរនៅ a[i - 1]។ ប្រសិនបើត្រូវការតែប្រវែង អ្នកអាចរក្សាតែពីរជួរជំនួសតារាងទាំងមូល ដើម្បីកាត់បន្ថយទំហំមក O(n)។ Edit distance (ចំនួនការបញ្ចូល ការលុប និងការជំនួសដែលបំប្លែងពាក្យមួយទៅពាក្យមួយទៀត) មានរូបរាងពីរវិមាត្រដូចគ្នា។

11. របៀបសម្គាល់បញ្ហា DP

បញ្ហា DP កម្រនិយាយថា "ប្រើ DP" ណាស់។ ចូរមើលរកសញ្ញាទាំងនេះ៖

វិធីសាស្ត្រដែលអាចទុកចិត្តបានសម្រាប់ interview៖

1. សរសេរ brute-force recursion មុនគេ ទោះបីយឺតក៏ដោយ។ និយាយថា input នៃ function មានន័យយ៉ាងណា។ ទាំងនេះគឺជា state របស់អ្នក។
2. កត់សម្គាល់ការហៅដដែលៗ។ នោះបញ្ជាក់ថាមាន overlapping subproblem។
3. បន្ថែម memo (top-down)។ ឥឡូវអ្នករួចរាល់ហើយ ជាមួយកូដត្រឹមត្រូវ។
4. ប្រសិនបើគេសួរ បំប្លែងវាទៅជា តារាង (bottom-up) រួចបង្រួមទំហំ។

ការធ្វើតាមលំដាប់នេះ មានន័យថាអ្នកតែងតែមានចម្លើយត្រឹមត្រូវក្នុងដៃ ហើយរាល់ជំហានក្រោយគឺជាការបង្កើនប្រសិទ្ធភាព។

ចុះរបៀបជ្រើសរវាង greedy និង DP? សាកល្បង greedy មុនលើឧទាហរណ៍តូចមួយ ហើយរក counterexample។ ប្រសិនបើអ្នកមិនអាចបំបែកវាបាន ហើយហេតុផលច្បាស់លាស់ (sort ផ្តល់លំដាប់ធម្មជាតិ) នោះ greedy ត្រឹមត្រូវ។ ប្រសិនបើអ្នករក counterexample បាន ឬជម្រើសធ្វើអន្តរកម្មគ្នា សូមទៅ DP។

12. រូបមន្ត៖ greedy.ts និង dp.ts សម្រាប់ algolab

បង្កើត src/greedy.ts៖

export interface Interval {
  start: number;
  end: number;
}

// Largest set of non-overlapping intervals (sort by end time).
export function maxNonOverlapping(intervals: Interval[]): Interval[] {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const chosen: Interval[] = [];
  let lastEnd = -Infinity;

  for (const iv of sorted) {
    if (iv.start >= lastEnd) {
      chosen.push(iv);
      lastEnd = iv.end;
    }
  }
  return chosen;
}

// Largest-coin-first change. Only correct for "nice" coin systems.
export function greedyCoins(coins: number[], amount: number): number[] {
  const sorted = [...coins].sort((a, b) => b - a);
  const used: number[] = [];
  let left = amount;

  for (const c of sorted) {
    while (left >= c) {
      used.push(c);
      left -= c;
    }
  }
  return left === 0 ? used : [];
}

បង្កើត src/dp.ts៖

export function fibMemo(
  n: number,
  memo = new Map<number, number>(),
): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

export function climbStairs(n: number): number {
  let a = 1;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

export function houseRobber(nums: number[]): number {
  let take = 0;
  let skip = 0;
  for (const n of nums) {
    [take, skip] = [skip + n, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

// Fewest coins to make `amount`, or -1 if impossible.
export function coinChange(coins: number[], amount: number): number {
  const dp = new Array<number>(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 0/1 knapsack: best total value within the capacity.
export function knapsack(
  items: { weight: number; value: number }[],
  capacity: number,
): number {
  const dp = new Array<number>(capacity + 1).fill(0);
  for (const { weight, value } of items) {
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

// Length of the longest common subsequence of two strings.
export function lcs(a: string, b: string): number {
  const dp: number[][] = Array.from({ length: a.length + 1 }, () =>
    new Array<number>(b.length + 1).fill(0),
  );
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] =
        a[i - 1] === b[j - 1]
          ? dp[i - 1][j - 1] + 1
          : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

បង្កើត src/dp.test.ts៖

import { test } from "node:test";
import assert from "node:assert/strict";
import { maxNonOverlapping, greedyCoins } from "./greedy.ts";
import {
  fibMemo,
  climbStairs,
  houseRobber,
  coinChange,
  knapsack,
  lcs,
} from "./dp.ts";

test("interval scheduling picks the most meetings", () => {
  const picked = maxNonOverlapping([
    { start: 1, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 11 },
  ]);
  assert.equal(picked.length, 3);
});

test("greedy coins works for nice systems, fails for odd ones", () => {
  assert.deepEqual(greedyCoins([25, 10, 5, 1], 63), [25, 25, 10, 1, 1, 1]);
  assert.equal(greedyCoins([4, 3, 1], 6).length, 3); // not optimal
  assert.equal(coinChange([4, 3, 1], 6), 2); // DP finds 3 + 3
});

test("fibonacci and stairs", () => {
  assert.equal(fibMemo(10), 55);
  assert.equal(fibMemo(50), 12586269025);
  assert.equal(climbStairs(5), 8);
  assert.equal(climbStairs(10), 89);
});

test("house robber", () => {
  assert.equal(houseRobber([2, 7, 9, 3, 1]), 12);
  assert.equal(houseRobber([1, 2, 3, 1]), 4);
});

test("coinChange", () => {
  assert.equal(coinChange([1, 2, 5], 11), 3);
  assert.equal(coinChange([5, 2], 3), -1);
  assert.equal(coinChange([1], 0), 0);
});

test("knapsack", () => {
  const items = [
    { weight: 1, value: 15 },
    { weight: 3, value: 20 },
    { weight: 4, value: 30 },
  ];
  assert.equal(knapsack(items, 4), 35);
});

test("lcs", () => {
  assert.equal(lcs("abcde", "ace"), 3);
  assert.equal(lcs("AGGTAB", "GXTXAYB"), 4);
  assert.equal(lcs("abc", "def"), 0);
});

រត់ test៖

npx tsx --test

ដើម្បីមានអារម្មណ៍ថាហេតុអ្វី memoization សំខាន់ ចូរវាស់ពេលវេលាកំណែយឺត ប្រៀបធៀបនឹងកំណែដែលមាន cache។ បង្កើត bench-fib.ts ក្នុងថត algolab៖

import { fibMemo } from "./src/dp.ts";

function fibSlow(n: number): number {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

console.time("fibSlow(35)");
console.log(fibSlow(35));
console.timeEnd("fibSlow(35)");

console.time("fibMemo(35)");
console.log(fibMemo(35));
console.timeEnd("fibMemo(35)");

npx tsx bench-fib.ts

ទាំងពីរបន្ទាត់បោះពុម្ព 9227465។ កំណែយឺតចំណាយរាប់សិបមិល្លីវិនាទី (ម៉ាស៊ីនរបស់អ្នកនឹងខុសគ្នា) ហើយកំណែ memoize គឺភ្លាមៗ។ ឥឡូវប្តូរ 35 ទៅ 45 សម្រាប់កំណែយឺត ហើយកត់សម្គាល់ថាពេលវេលាកើនលឿនប៉ុណ្ណា ចំណែកកំណែ memoize នៅតែចប់ភ្លាមៗ។

13. សាកល្បងដោយខ្លួនឯង

1. បំបែក greedy។ រកតម្លៃកាក់ (ក្រៅពី [4, 3, 1]) ដែល greedy ផ្តល់ចម្លើយខុសសម្រាប់ចំនួនមួយ។ បញ្ជាក់ដោយប្រើ greedyCoins និង coinChange ទន្ទឹមគ្នា។ បន្ទាប់មកពិនិត្យថាកាក់អាមេរិក [25, 10, 5, 1] មិនដែលមិនស៊ីគ្នាសម្រាប់ចំនួន 0 ដល់ 200។
2. ចំនួនបន្ទប់អប្បបរមា។ ដោយមាន interval ប្រជុំ ចូររកចំនួនបន្ទប់តិចបំផុតដែលត្រូវការ ដើម្បីកុំឲ្យការប្រជុំពីរក្នុងបន្ទប់ដូចគ្នាត្រួតគ្នា។ ជំនួយ៖ sort តាមម៉ោងចាប់ផ្តើម ហើយរក្សា min-heap នៃម៉ោងបញ្ចប់ (ជំពូកទី 10)។ (បញ្ហាបុរាណក្នុង interview។)
3. វិធីបង្កើតការអាប់លុយ។ ផ្លាស់ប្តូរ coinChange ឲ្យ រាប់ ថាតើមានបន្សំកាក់ខុសគ្នាប៉ុន្មានដែលបង្កើតបានចំនួននោះ (លំដាប់មិនសំខាន់)។ ជំនួយ៖ ដាក់ loop កាក់នៅ ខាងក្រៅ ហើយបូកជំនួសឲ្យការយកតម្លៃតូចបំផុត។ សម្រាប់ [1, 2, 5] និង 5 ចម្លើយគឺ 4។
4. ផលបូកផ្លូវអប្បបរមា។ ក្នុងក្រឡាចត្រង្គនៃលេខមិនអវិជ្ជមាន ផ្លាស់ទីបានតែទៅស្តាំ ឬចុះក្រោមពីជ្រុងខាងលើឆ្វេងទៅជ្រុងខាងក្រោមស្តាំ ដោយកាត់បន្ថយផលបូកនៃក្រឡាដែលបានឆ្លងកាត់។ កំណត់ state dp[r][c] ហើយសរសេរ recurrence។ (បែប interview។)
5. Longest increasing subsequence។ សម្រាប់ [10, 9, 2, 5, 3, 7, 101, 18] ចម្លើយគឺ 4 (2, 3, 7, 18)។ ប្រើ dp[i] ជា increasing subsequence វែងបំផុតដែល បញ្ចប់ នៅ index i។ វាគឺ O(n^2)៖ បន្ទាប់មកសូមស្វែងរកកំណែ O(n log n) ដែលប្រើ binary search (ជំពូកទី 7)។
6. Edit distance។ សរសេរ editDistance(a, b) ដែលត្រឡប់ចំនួនការបញ្ចូល ការលុប និងការជំនួសតិចបំផុត ដើម្បីបំប្លែង a ទៅជា b។ សម្រាប់ "kitten" និង "sitting" ចម្លើយគឺ 3។ វាមានរូបរាងតារាងដូច lcs។

Greedy យកជម្រើសដែលមើលទៅល្អបំផុត ហើយមិនមើលក្រោយវិញឡើយ។ Dynamic programming ដោះស្រាយបញ្ហាតូចនីមួយៗម្តង ហើយចងចាំចម្លើយ។ រវាងទាំងពីរ អ្នកអាចដោះស្រាយសំណួរ "វិធីល្អបំផុតដើម្បី" ភាគច្រើន។ នៅក្នុងជំពូកចុងក្រោយ ដាក់ឲ្យរួមគ្នា យើងប្រមូល structure និងបច្ចេកទេសទាំងអស់ពីស៊េរីនេះចូលទៅក្នុង pattern cheat sheet, អនុវត្តវិធីសាស្ត្រជំហានម្តងមួយៗសម្រាប់បញ្ហា interview និងភ្ជាប់ module algolab ទាំងអស់ចូលជា package មួយ។