Dynamic Programming - Common Patterns
LeetCode בדק את כל 100 השאלות הנפוצות ביותר בראיונות והגיע למסקנה: 68% מהן שייכות לאחד מחמישה Patterns. Knapsack הוא אחד מהם. מי שמכיר אותו פותר Partition Equal Subset Sum, Target Sum, ו-Combination Sum תוך דקות. מי שלא - מתחיל מאפס בכל פעם.
DP Patterns הם כמו Vocabulary - ברגע שיש לכם 5-6 Patterns, פתרון בעיה חדשה הופך ל-"זה נראה כמו Knapsack" במקום "מה אני עושה כאן?" השיעור הזה מלמד את ה-Vocabulary המרכזי.
מה שמפריד בין DP "שמבינים" לDP "ששיננתם" הוא יכולת הזיהוי. כשמועמד מתבקש לפתור Partition Equal Subset Sum ואומר מיד "זה Knapsack Variant" - המראיין מבין שיש Vocabulary DP אמיתי, לא שינון LeetCode. הVocabulary הזה בנוי מחמישה Patterns שמכסים את רוב שאלות ה-DP בראיונות, ולימוד כל Pattern עם שתי-שלוש דוגמאות מספיק כדי לזהות Variants חדשים.
הגישה הנכונה ללמוד DP Patterns: לא "לזכור פתרון לכל שאלה" אלא "להבין מה הTemplate ולמה הוא עובד." ב-Knapsack, ה-Template הוא dp[i][w] = max(skip, take) - שני מקרים בלבד. כשמבינים שכל שאלת Knapsack מתרחשת לשני המקרים האלה, אפשר לבנות את הפתרון מחדש על Variant שמעולם לא ראיתם. זו היכולת שמראיינים מחפשים.