تخيل إنك بتحل امتحان فيه أسئلة متشابهة:
"Don't repeat yourself" - ما تحلش نفس المشكلة مرتين!
الحل الأمثل للمشكلة الكبيرة = تجميع حلول المشاكل الصغيرة
نفس المشكلة الصغيرة بتتكرر كتير - نحفظها!
ابدأ من المشكلة الكبيرة، احفظ النتايج
استخدم Recursion + Cache
ابدأ من المشاكل الصغيرة، ابني الحل
استخدم Loop + Table
المثال الكلاسيكي لفهم DP
كل رقم = مجموع الرقمين اللي قبله
fib(n) = fib(n-1) + fib(n-2)
fib(5) calls:
fib(5) → fib(4) + fib(3)
fib(4) → fib(3) + fib(2)
fib(3) calculated TWICE! 😱
Exponential - بطيء جداً!
fib(5) with cache:
fib(5) → fib(4) + cache[3]
fib(4) → fib(3) + cache[2]
Each value calculated ONCE! ✓
Linear - سريع جداً!
Enter n and click Calculate.
عندك شنطة بسعة معينة، إزاي تملاها بأغلى حاجات؟
أقل عدد عملات تعمل بيها مبلغ معين؟
أطول subsequence مشتركة بين كلمتين؟
كام طريقة تصعد n درجة (1 أو 2 في المرة)؟
function fib(n, memo = {}) {
// Base cases
if (n <= 1) return n;
// Check cache
if (n in memo) return memo[n];
// Calculate & store
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}💡 الفكرة:
قبل ما نحسب، نشوف لو محسوبة قبل كده!
function fib(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}💡 الفكرة:
نبني الجدول من الأول للآخر step by step