Dynamic Programming - Fundamentals
ראיון ב-Google, 2023. "Climbing Stairs - you can take 1 or 2 steps, how many ways to reach step n?" מועמד ראשון: רקורסיה נאיבית, מחשב fib(50) תוך שניות של Timeout. מועמד שני: "זה Fibonacci עם Memoization" - 5 שורות, O(n), ועבר. ה-Gap: מי הכיר DP כ-Pattern ומי לא.
Dynamic Programming הוא הנושא שהכי פעמים נשמעת הטענה: "הבנתי DP, אבל בבעיה חדשה אני לא יודע איך להתחיל." זה סימן שהבנתם את ה-Mechanics אבל לא את ה-Process - הסדר המסוים שבו מתקדמים מבעיה חדשה לפתרון. שיעור זה מלמד את ה-Process, לא רק את ה-Mechanics.
Dynamic Programming הוא הנושא שהכי הרבה מועמדים מפחדים ממנו - ולא בצדק. DP הוא לא קסם. זה Recursion + Caching. ברגע שמבינים את הנוסחה הרקורסיבית, השאר הוא שיטה.