🧠 धडा 11 — Dynamic programming आणि greedy: फळ्यावरची उत्तरे

📍 तुम्ही इथे आहात: 12 पैकी धडा 11 · पुढे: lesson-12-choosing

📦 या ब्रँचमध्ये काय आहे

धडे 01–11. exponential recursion चे linear table मध्ये रूपांतर, चार पायऱ्यांची कृती, आणि proof सांगेल तेव्हाच चालणारा shortcut.

dsa/algorithms.py — fib_memo, stairs, coin_change, max_meetings
dsa/demo.py — dp

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

मुख्याध्यापिकेने fib(25) 242,785 वेळा विचारले होते, आठवते? कॉरिडॉरमध्ये एक फळा लावा: पहिल्यांदा कोणी "fib(17) = 1597" असे उत्तर दिले की ते तिथे लिहा. पुढच्या वेळी ज्याला विचारले जाईल तो त्याऐवजी फळा पाहतो. आता प्रत्येक प्रश्नाचे उत्तर एकदाच काढले जाते: एकूण 49. हे memoisation. किंवा फळा स्वतःच खालून भरा — fib(0), fib(1), fib(2)… — कोणालाही न विचारता: हे tabulation.

Greedy वेगळे आहे: फळा नाही, प्रत्येक वेळी फक्त सर्वात चांगली दिसणारी पायरी घ्या. एका खोलीत जास्तीत जास्त club meetings बसवायला, नेहमी आधी संपणारी meeting घ्या. हे चालते — त्याचा proof आहे. 1, 3 आणि 4 च्या नाण्यांनी 6 बनवताना "आधी सर्वात मोठे नाणे" 4+1+1 = तीन नाणी देते; फळा सांगतो 3+3 = दोन. कोणीतरी सिद्ध केले असेल तरच greedy बरोबर असतो.

🗺️ आकृती

flowchart LR
  S0["stairs(0)=1"] --> S1["stairs(1)=1"] --> S2["stairs(2)=2"] --> S3["stairs(3)=3"] --> S4["stairs(4)=5"] --> Sn["… stairs(n) = stairs(n−1) + stairs(n−2)"]

❓ काय

problem मध्ये overlapping sub-problems (तोच छोटा प्रश्न पुन्हा पुन्हा विचारला जातो) आणि optimal substructure (सर्वोत्तम उत्तर छोट्या प्रश्नांच्या सर्वोत्तम उत्तरांपासून बनते) असतील तेव्हा DP लागू होते.
कृती: state (sub-problem कसा दिसतो?) → recurrence (तो छोट्या states वर कसा अवलंबून आहे?) → base cases → order (top-down memo किंवा bottom-up table) → उत्तर.
stairs(n): ways = stairs(n−1) + stairs(n−2), O(n). coin_change: best[a] = 1 + min(best[a−c]), O(amount × coins). क्लासिक उदाहरणे: knapsack, edit distance, longest common subsequence, grid paths.
Greedy: स्थानिक पातळीवर सर्वोत्तम पर्याय, कधीही पुन्हा न तपासलेला; O(n log n) किंवा O(n); फक्त exchange argument असेल तरच बरोबर — interval scheduling, Huffman, Dijkstra, canonical coin systems.

🤔 का

optimisation problems च्या मोठ्या कुटुंबासाठी DP म्हणजे "सेकंदांत चालते" आणि "विश्वाचा अंत होईपर्यंतही संपणार नाही" यांतला फरक; greedy म्हणजे हुशार O(n log n) आणि चुकीचे उत्तर यांतला फरक. कोणते कोणते हे ओळखणे हेच कौशल्य.

🔧 कसे (या repo मध्ये)

fib_memo recursion ला dict जोडतो; stairs दोन variables फिरवत ठेवतो; coin_change सर्वोत्तम counts चे table भरतो आणि अशक्य असेल तर −1 परत करतो; max_meetings end time नुसार sort करतो आणि जे बसते ते घेतो.

🧪 करून पाहा

python3 dsa/demo.py dp
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import coin_change
def greedy(coins, amount):
    n = 0
    for c in sorted(coins, reverse=True): n += amount // c; amount %= c
    return n if amount == 0 else -1
for coins, amt in (([1, 5, 10, 25], 63), ([1, 3, 4], 6), ([4, 7], 5)):
    print(coins, amt, "greedy:", greedy(coins, amt), "DP:", coin_change(coins, amt))
# edit distance in four steps: state (i, j) · recurrence min(replace, insert, delete) · base i or j = 0 · bottom-up
def edit(a, b):
    T = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            T[i][j] = j if i == 0 else i if j == 0 else min(T[i-1][j-1] + (a[i-1] != b[j-1]), T[i-1][j] + 1, T[i][j-1] + 1)
    return T[-1][-1]
print("edit('kitten', 'sitting') =", edit("kitten", "sitting"))
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

stairs(10) = 89, coin_change([1,5,10,25], 63) = 6, [4,7] ने 5 बनवणे -1, meetings ['chess', 'coding', 'art']. US-प्रकारच्या नाण्यांसाठी greedy DP शी सहमत होतो, [1,3,4] साठी DP 2 देते तिथे greedy 3 देतो, आणि edit distance 3 आहे.

🏁 तुम्ही आत्ताच काय सिद्ध केले

फळ्याच्या मदतीने तुम्ही exponential recursion linear केले, table bottom-up भरले, आणि तीन नाण्यांच्या उदाहरणाने greedy ला चुकताना पकडले.

⚠️ नेहमीच्या चुका

mutable किंवा unhashable state वर memoise करणे (tuples वापरा).
tabulation मध्ये क्रम चुकणे (cell भरण्याआधीच वाचली जाते).
"उदाहरणांवर चालले" म्हणून proof शिवाय greedy वर विश्वास ठेवणे.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: diff tools (edit distance), spell checkers, resource allocation, text wrapping, आणि पर्यायांवरचा प्रत्येक "सर्वात कमी / सर्वात जास्त / सर्वात स्वस्त" प्रश्न — DP किंवा सिद्ध केलेला greedy, अंदाज कधीच नाही.

⏭️ पुढे

धडा 12 — योग्य structure निवडणे: प्रश्न ठरवतो, आणि कळस-प्रकल्प (capstone).

🧠 Lesson 11 — Dynamic programming & greedy: answers on the board

📍 You are here: Lesson 11 of 12 · Next: lesson-12-choosing

📦 What's in this branch

Lessons 01–11. Turning an exponential recursion into a linear table, the four-step recipe, and the shortcut that works only when a proof says so.

dsa/algorithms.py — fib_memo, stairs, coin_change, max_meetings
dsa/demo.py — dp

🧒 Explain like I'm 5

Remember the head asking fib(25) 242,785 times? Put a board in the corridor: the first time anyone answers "fib(17) = 1597", write it up. The next person to be asked looks at the board instead. Now every question is answered once: 49 in all. That is memoisation. Or fill the board yourself from the bottom — fib(0), fib(1), fib(2)… — never asking anyone: that is tabulation.

Greedy is different: no board, just take the best-looking step every time. To fit the most club meetings into one room, always take the meeting that ends first. It works — there is a proof. For coins of 1, 3 and 4 making 6, "biggest coin first" gives 4+1+1 = three coins; the board says 3+3 = two. Greedy is only right when someone proved it.

🗺️ Diagram

flowchart LR
  S0["stairs(0)=1"] --> S1["stairs(1)=1"] --> S2["stairs(2)=2"] --> S3["stairs(3)=3"] --> S4["stairs(4)=5"] --> Sn["… stairs(n) = stairs(n−1) + stairs(n−2)"]

❓ What

DP applies when a problem has overlapping sub-problems (the same smaller question asked repeatedly) and optimal substructure (the best answer is built from best answers to smaller ones).
The recipe: state (what does a sub-problem look like?) → recurrence (how does it depend on smaller states?) → base cases → order (top-down memo or bottom-up table) → answer.
stairs(n): ways = stairs(n−1) + stairs(n−2), O(n). coin_change: best[a] = 1 + min(best[a−c]), O(amount × coins). Classics: knapsack, edit distance, longest common subsequence, grid paths.
Greedy: locally best choice, never revisited; O(n log n) or O(n); correct only with an exchange argument — interval scheduling, Huffman, Dijkstra, canonical coin systems.

🤔 Why

DP is the difference between "runs in seconds" and "would not finish before the heat death of the universe" for a large family of optimisation problems; greedy is the difference between a clever O(n log n) and a wrong answer. Knowing which is which is the skill.

🔧 How (in this repo)

fib_memo adds a dict to the recursion; stairs rolls two variables; coin_change fills a table of best counts and returns −1 when impossible; max_meetings sorts by end time and takes what fits.

🧪 Try it

python3 dsa/demo.py dp
python3 - <<'EOF'
import sys; sys.path.insert(0, "dsa"); from algorithms import coin_change
def greedy(coins, amount):
    n = 0
    for c in sorted(coins, reverse=True): n += amount // c; amount %= c
    return n if amount == 0 else -1
for coins, amt in (([1, 5, 10, 25], 63), ([1, 3, 4], 6), ([4, 7], 5)):
    print(coins, amt, "greedy:", greedy(coins, amt), "DP:", coin_change(coins, amt))
# edit distance in four steps: state (i, j) · recurrence min(replace, insert, delete) · base i or j = 0 · bottom-up
def edit(a, b):
    T = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            T[i][j] = j if i == 0 else i if j == 0 else min(T[i-1][j-1] + (a[i-1] != b[j-1]), T[i-1][j] + 1, T[i][j-1] + 1)
    return T[-1][-1]
print("edit('kitten', 'sitting') =", edit("kitten", "sitting"))
EOF

✅ Verify — what you should see

stairs(10) = 89, coin_change([1,5,10,25], 63) = 6, [4,7] making 5 is -1, meetings ['chess', 'coding', 'art']. Greedy agrees with DP for the US-style coins, gives 3 where DP gives 2 for [1,3,4], and edit distance is 3.

🏁 What you just proved

You turned an exponential recursion into a linear one with a board, filled a table bottom-up, and caught greedy being wrong with a three-coin example.

⚠️ Common mistakes

Memoising on a mutable or unhashable state (use tuples).
Getting the order wrong in tabulation (a cell read before it is filled).
Trusting greedy without a proof because it "worked on the examples".

🏭 Why this matters in production: diff tools (edit distance), spell checkers, resource allocation, text wrapping, and every "fewest / most / cheapest" question over choices — DP or a proven greedy, never a guess.

⏭️ Next

Lesson 12 — choosing the right structure: the question decides, and the capstone.

← Previousgraphs Next →choosing

This page is the lesson's README from the lesson-11-dp-greedy branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.