Dynamic Programming — সময়ের মধ্যে শেখার পরিকল্পনা

আপনার একটি target topic order আছে এবং কয়েকটি ছোট lesson আছে। প্রতিটি lesson-এর topic order target-এর সঙ্গে কতটা মেলে, তা LCS দিয়ে score করবেন। তারপর নির্দিষ্ট সময়ের মধ্যে lesson বেছে সেই score-এর যোগফল সর্বোচ্চ করবেন। প্রথম DP-এর result দ্বিতীয় DP-এর value হবে।

Microsoft কোর্সের সংযোগ: Module 4-এর dynamic programming ও problem-solving। এখানে state, transition, reconstruction এবং 0/1 choice সরাসরি অনুশীলন হবে।

১. আগে পড়া ও অনুশীলনের ক্রম

ক্রম	উপকরণ	যা বলতে পারবেন
১	DP ধারণা, State-transition thinking	State-এর অর্থ, base case, recurrence
২	Visual explanation, Fibonacci তিনভাবে	একই subproblem বারবার এলে table কেন
৩	Longest Common Subsequence	Subsequence বনাম substring, 2D prefix state
৪	Book Shop knapsack	Take/skip এবং একটি item একবার নেওয়া
৫	DP patterns	Table থেকে কোন choice নেওয়া হয়েছিল উদ্ধার করা

প্রথমে AC ও ABCD-এর LCS table পূরণ করুন। তারপর দুই lesson-এর ছোট budget table হাতে করুন। Table-এর প্রতিটি ঘরের অর্থ একটি পূর্ণ বাক্যে না বলতে পারলে পরের ধাপে যাবেন না।

২. সমস্যা ও scoring rule

study_plan(lessons, target, budget) লিখুন। প্রতিটি lesson (id, minutes, topic_sequence)। Topic-কে এক অক্ষরের symbol হিসেবে ধরুন: যেমন A=array, B=search, C=tree, D=graph। Symbol-এর নির্দিষ্ট mapping আপনার course note-এ লেখা থাকবে; algorithm শুধু symbol মেলে।

1. প্রতিটি lesson-এর sequence ও target-এর LCS length হলো lesson score। Matched subsequence-টিও report-এ দিন।
2. প্রতিটি lesson সর্বোচ্চ একবার নিন। মোট minutes budget-এর সমান বা কম রেখে score-এর যোগফল সর্বোচ্চ করুন।
3. Score সমান হলে DP-এর current lesson skip করুন; অর্থাৎ আগের row-এর plan রাখুন। Minimum minutes আলাদা objective নয়।
4. Chosen ID input order-এ, ব্যবহৃত minutes, সর্বোচ্চ score এবং সব lesson-এর alignment ফেরত দিন।

Scoring স্পষ্ট করে নিন: দুটি selected lesson-এ একই topic মিললে সেটি দুবার score পাবে। এটি rehearsal/alignment score, unique topic coverage নয়। Target-এর length 4 হলেও total score 5 হতে পারে। Unique coverage optimize করতে অন্য state লাগবে।

সীমা: 0 ≤ lesson_count ≤ 80, 0 ≤ budget ≤ 2,000, positive integer minutes, প্রতিটি sequence ও target সর্বোচ্চ 100 symbol; ID আলাদা string। Negative budget, nonpositive duration বা duplicate ID-তে ValueError। Empty target/lesson sequence বৈধ; তখন সংশ্লিষ্ট score 0। Input অপরিবর্তিত রাখুন।

Python

study_plan(
    [("A", 3, "AC"), ("B", 4, "ABD"), ("C", 2, "BC")],
    target="ABCD",
    budget=6,
)

Lesson	Minutes	Matched topics	Score
A	3	AC	2
B	4	ABD	3
C	2	BC	2

A+B-এর সময় 7, তাই নেওয়া যায় না। A+C-তে score 4, সময় 5। B+C-তে score 5, সময় 6; এটিই উত্তর। B topic দুই lesson-এ গণনা হয়েছে।

Python

{
    "chosen": ["B", "C"], "minutes": 6, "score": 5,
    "alignment": [
        {"id": "A", "matched": "AC", "score": 2},
        {"id": "B", "matched": "ABD", "score": 3},
        {"id": "C", "matched": "BC", "score": 2},
    ],
}

flowchart LR
    seq["Lesson sequence + target"] --> lcs["LCS table\nscore ও matched topics"]
    lcs --> items["minutes, score item"]
    items --> pack["0/1 knapsack\ntake অথবা skip"]
    pack --> trace["Table ধরে পেছনে হাঁটা"]
    trace --> report["Chosen ID, minutes, score"]

৩. চার ধাপের guided problem

A — LCS state ও transition

lcs[i][j] হবে lesson-এর প্রথম i symbol ও target-এর প্রথম j symbol-এর LCS length। একটি prefix খালি হলে উত্তর 0। শেষ symbol মিললে diagonal+1; না মিললে ওপর/বামের maximum।

Invariant: lcs[i][j] পড়ার সময় তার দরকারি ছোট prefix state তৈরি আছে। Checkpoint: AC ও ABCD-এর final score 2; AB ও BA-এর score 1, 2 নয়।

B — Matched sequence উদ্ধার

শেষ cell থেকে পেছনে হাঁটুন। Symbol মিললে সেটি সংগ্রহ করে diagonal-এ যান। না মিললে বড় neighbor-এর দিকে যান; সমান হলে ওপরের cell নিন। শেষে collected symbol reverse করুন।

Checkpoint: Recovered sequence দুই input-এরই subsequence হতে হবে এবং length table-এর score-এর সমান। একাধিক LCS হলে যেকোনো valid witness ঠিক; reference-এর ওপর-আগে tie rule deterministic ফল দেয়।

C — Lesson নির্বাচন

best[i][b] মানে প্রথম i lesson-এর মধ্যে budget b-তে সর্বোচ্চ score। Skip: best[i-1][b]। Take সম্ভব হলে: score[i-1] + best[i-1][b-minutes[i-1]]।

Invariant: Take-এর পরে আগের row পড়বেন; বর্তমান row পড়লে একই lesson বারবার নেওয়া হয়ে যেতে পারে। Checkpoint: একটি ২-minute, ২-score lesson আর budget 20 হলেও answer 2, 20 নয়।

D — Plan reconstruction ও final audit

best[n][budget] থেকে আগের row-এর সঙ্গে তুলনা করুন। সমান হলে skip। আলাদা হলে current lesson নেওয়া হয়েছে; budget থেকে তার minutes বাদ দিয়ে আগের row-এ যান। Chosen list reverse করুন।

Checkpoint: example-এ C নেওয়ার পরে remaining budget 4; B নিলে 0। Chosen lesson-এর duration sum 6, alignment score sum 5। এই দুটি report-এর সংখ্যার সঙ্গে মিলতে হবে।

৪. সমাধান বুঝে মিলিয়ে দেখুন

দুটি DP-এর correctness

LCS-এর শেষ symbol মিললে তাকে শেষ match ধরে ছোট prefix-এর optimal answer বাড়ানো যায়; না মিললে অন্তত এক পাশের শেষ symbol বাদ যাবে। দুই choice-এর maximum-ই উত্তর।

Knapsack-এ প্রতিটি plan-এর শেষ lesson হয় নেওয়া হয়েছে, নয়তো হয়নি। এই দুই ভাগ সব valid plan cover করে; আগের row ব্যবহারে একটি lesson একবারের বেশি নেওয়া যায় না। প্রথম DP-এর score দ্বিতীয় DP-তে value হিসেবে যায়, তাই দুই কাজ বিচ্ছিন্ন exercise নয়।

Python solution · unit test।

৫. Test ও complexity

Repository root থেকে; download করলে দুই ফাইল practice/-এ রেখে:

Bash

python -m unittest discover -s practice -p 'test_dynamic_programming_lab.py' -v

৮টি test method example, empty/zero case, unrelated topics, item reuse, tie rule, repeated symbol ও invalid input দেখে। ৭০টি seeded ছোট case-এ LCS সব subsequence enumerate করে এবং lesson selection সব subset enumerate করে যাচাই হয়। Chosen plan-এর score, duration ও uniqueness-ও পরীক্ষা হয়।

N lesson, B budget, target length T, lesson length Lᵢ হলে time O(T × ΣLᵢ + NB)। LCS table একবারে একটি lesson-এর জন্য থাকে; knapsack reconstruction-এর table-সহ space O(T × max Lᵢ + NB) এবং report storage। Table কমিয়ে one-dimensional করলে reconstruction-এর জন্য অতিরিক্ত পরিকল্পনা দরকার।

৬. Coverage ও বাকি অনুশীলন

এখানে শিখলেন	আলাদা করে করবেন
Prefix-based 2D DP ও LCS	Edit distance
0/1 take-skip, budget state	Coin combinations-এ reuse ও counting
Optimal value থেকে solution উদ্ধার	LIS
Base case, transition, tie rule	Grid paths, interval DP

একটি capstone-এ DP-এর সব state shape নেই। সব DP problem থেকে remaining pattern করুন।