Dynamic Programming
ডায়নামিক প্রোগ্রামিং
Overlapping subproblem-এর উত্তর একবার বের করে জমা রেখে বারবার ব্যবহার করা technique — exponential recursion-কে polynomial-এ নামায়।
also: dp, memoization, tabulation
দুটো শর্ত থাকলে DP কাজ করে:
- Optimal substructure — বড় সমস্যার optimal উত্তর ছোটগুলোর optimal উত্তর থেকে বানানো যায়
- Overlapping subproblems — একই ছোট সমস্যা বারবার ফিরে আসে
Naive Fibonacci O(φⁿ); উত্তর জমা রাখলে O(n):
fib = [0] * (n + 1); fib[1] = 1
for i in range(2, n + 1):
fib[i] = fib[i - 1] + fib[i - 2]উপর-থেকে-নিচ memoization (recursion + cache) আর নিচ-থেকে-উপর tabulation (loop + table) — একই খরচ, ভিন্ন স্বাদ। Shortest path (Floyd-Warshall), edit distance, knapsack, parsing — সব DP-র ছাত্র।