DP: একই ছোট প্রশ্নের উত্তর পুনরায় ব্যবহার

অধ্যায়ের সূচি · অনুশীলন ও সমাধান · মূল ধারণা

DP-তে table আঁকার আগে একটি বাক্য লিখুন: এই cell কী প্রশ্নের উত্তর? dp[i] কখনো প্রথম iটি item-এর উত্তর, কখনো ঠিক i-তে শেষ হওয়া উত্তরের মান। এই দুই অর্থ মিশে গেলে code দেখতে ঠিক হলেও ফল ভুল হবে।

শেখার ক্রম

ধাপ	পড়া	লক্ষ্য
1	Repeated subproblem ও memoization	কোন প্রশ্ন বারবার হচ্ছে তা খুঁজে পাওয়া
2	Table-এর প্রতিটি ধাপ	Known cell থেকে next cell হিসাব
3	State → transition → base → order → answer	Code-এর আগে পাঁচটি বাক্য লেখা
4	Pattern-এর তুলনা	Counting, minimum, boolean আলাদা করা
5	Implementation ও problem tracker	নিজের trace-এর সঙ্গে output মেলানো

একটি প্রোগ্রাম: নির্দিষ্ট দৈর্ঘ্যের জন্য কম প্যাকেট

ধরি একটি delivery service-এ 1, 3 ও 4 ইউনিটের packet আছে; প্রত্যেকটি যতবার খুশি নেওয়া যায়। মোট 6 ইউনিট পাঠাতে সর্বনিম্ন কয়টি packet লাগবে? বড়টি আগে নিলে 4+1+1 = 3টি। কিন্তু 3+3 = 2টি। তাই এই denomination-এ greedy যথেষ্ট নয়।

State: dp[s] = ঠিক s ইউনিট বানাতে সর্বনিম্ন packet। Base: dp[0]=0। Transition: শেষ packet c হলে বাকি s-c; তাই dp[s]=1+min(dp[s-c]), কেবল c<=s বিবেচনা করুন।

s	শেষ 1	শেষ 3	শেষ 4	dp[s]	একটি পছন্দ
0	—	—	—	0	খালি
1	1+dp[0]=1	—	—	1	[1]
2	1+dp[1]=2	—	—	2	[1,1]
3	1+dp[2]=3	1+dp[0]=1	—	1	[3]
4	1+dp[3]=2	1+dp[1]=2	1+dp[0]=1	1	[4]
5	1+dp[4]=2	1+dp[2]=3	1+dp[1]=2	2	[4,1]
6	1+dp[5]=3	1+dp[3]=2	1+dp[2]=3	2	[3,3]

flowchart LR
  zero["dp[0] = 0"] -->|"শেষ packet 3"| three["dp[3] = 1"]
  three -->|"শেষ packet 3"| six["dp[6] = 2"]
  two["dp[2] = 2"] -->|"শেষ packet 4: মোট 3"| six
  five["dp[5] = 2"] -->|"শেষ packet 1: মোট 3"| six

প্রতিটি dependency ছোট sum-এর দিকে, তাই s=1 থেকে 6 ক্রমে table ভরা যায়। amount=A, coin type k হলে সময় O(Ak), space O(A)। এই সীমা amount-এর উপর নির্ভর করে; A অনেক বড় হলে শুধু coin type কম বলে code দ্রুত হবে না।

একই data, ভিন্ন প্রশ্ন

প্রশ্ন	State-এর মান	একাধিক choice মিলবে কীভাবে	Base
সর্বনিম্ন coin কত	সংখ্যা বা infinity	min	dp[0]=0
কোনো subset দিয়ে sum হয় কি	True/False	OR	dp[0]=True
Ordered sequence কতটি	count	যোগ	dp[0]=1
সর্বোচ্চ লাভ কত	best value	max	খালি নির্বাচন বৈধ হলে 0

Coin [2,3,5] দিয়ে sum 5-এর ordered sequence [2,3], [3,2], [5]: মোট 3। Coin Combinations I-এর সম্পূর্ণ table দেখুন। Counting-এ dp[0]=1 মানে একটি খালি sequence; এটি সব প্রথম coin যোগ করার ভিত্তি।

Loop-এর দিক কেন অর্থ বদলায়

একটি item একবারই নেওয়া গেলে 1D knapsack-এ capacity বড় থেকে ছোট ঘুরুন। নইলে এই item দিয়ে আপডেট হওয়া ছোট capacity পড়ে একই item দ্বিতীয়বার ব্যবহার হয়ে যেতে পারে। একই coin বারবার নেওয়া বৈধ হলে এই পুনর্ব্যবহারই দরকার।

বাস্তব প্রয়োগে Edit Distance string-এর মিল মাপে, Book Shop budget-এর মধ্যে selection শেখায়, আর DAG-এর longest path dependency-ভিত্তিক কাজের পরিকল্পনার ভিত্তি। প্রতিটি ক্ষেত্রে আগে state-এর অর্থ ও constraints লিখুন।