""" Dynamic programming — সাতটা classic-এর reference implementation। পড়ার order মেলে state-transition-thinking.md-এর সাথে। প্রতিটা function তার docstring-এ 5-step doctrine বহন করে: 1. STATE dp[...] মানে কী, শব্দে 2. TRANSITION equation-টা 3. BASE CASES 4. FILL ORDER 5. ANSWER কোন cell-এ থাকে Standard library only। File-টা চালাও: সব assert pass করতেই হবে। """ # --------------------------------------------------------------------------- # 0. Fibonacci তিনভাবে — concept.md-র concept demo # --------------------------------------------------------------------------- def fib_naive(n): """সাধারণ recursion। সঠিক কিন্তু exponential: সবকিছু আবার solve করে। শুধু পাশাপাশি তুলনার জন্য রাখা; n > ~30 দিয়ে কখনো call কোরো না। """ if n <= 1: return n return fib_naive(n - 1) + fib_naive(n - 2) def fib_memo(n, memo=None): """Top-down DP: সেই একই recursion plus একটা খাতা (dict)। Solve করার আগে খাতা দেখো; solve করার পরে লিখে রাখো। প্রতিটা distinct n ঠিক একবার computed হয় -> O(n) time। """ if memo is None: memo = {} if n in memo: # আগেই উত্তর দেওয়া? দেখে নাও return memo[n] if n <= 1: return n memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n] def fib_tab(n): """Bottom-up DP: খাতাটা order-এ ভরো, একটা loop দিয়ে। STATE dp[i] = i-তম Fibonacci number TRANSITION dp[i] = dp[i-1] + dp[i-2] BASE dp[0] = 0, dp[1] = 1 FILL ORDER i = 2 .. n ANSWER dp[n] (Space note: শুধু আগের দুটো cell পড়া হয় -> O(1) space সম্ভব।) """ if n <= 1: return n prev2, prev1 = 0, 1 # পুরো array-র বদলে rolling window for _ in range(2, n + 1): prev2, prev1 = prev1, prev2 + prev1 return prev1 # --------------------------------------------------------------------------- # 1. Climbing stairs (LeetCode 70) — 1D linear DP # --------------------------------------------------------------------------- def climbing_stairs(n): """1 বা 2 ধাপ করে n সিঁড়ি ওঠার ways গোনো। STATE dp[i] = step i-তে দাঁড়ানোর distinct ways-এর সংখ্যা TRANSITION dp[i] = dp[i-1] + dp[i-2] (শেষ লাফটা ছিল 1 বা 2) BASE dp[0] = 1 (দাঁড়িয়ে থাকো), dp[1] = 1 FILL ORDER i = 2 .. n ANSWER dp[n] """ dp = [0] * (n + 1) dp[0] = 1 if n >= 1: dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] # --------------------------------------------------------------------------- # 2. House robber (LeetCode 198) — 1D take-or-skip # --------------------------------------------------------------------------- def house_robber(money): """এক সারি বাড়ি থেকে max লুট, পাশাপাশি দুটো কখনোই নয়। STATE dp[i] = বাড়ি 0..i থেকে max লুট TRANSITION dp[i] = max(dp[i-1], বাড়ি i skip করো dp[i-2] + money[i]) লুট করো (i-1 নিষিদ্ধ) BASE dp[0] = money[0]; dp[1] = max(money[0], money[1]) FILL ORDER i = 2 .. n-1 ANSWER dp[n-1] """ n = len(money) if n == 0: return 0 if n == 1: return money[0] dp = [0] * n dp[0] = money[0] dp[1] = max(money[0], money[1]) for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + money[i]) return dp[n - 1] # --------------------------------------------------------------------------- # 3. Coin change, minimum coins (LeetCode 322) — unbounded knapsack (min) # --------------------------------------------------------------------------- def coin_change(coins, amount): """`amount` বানাতে সবচেয়ে কম coin (unlimited supply), নাহলে -1। STATE dp[a] = ঠিক amount a বানাতে min coin TRANSITION dp[a] = 1 + min(dp[a - c]) — c <= a এমন coin-গুলোর উপর BASE dp[0] = 0; বাকি সব শুরু হয় infinity দিয়ে FILL ORDER a = 1 .. amount (বাঁ থেকে ডান = item reusable) ANSWER dp[amount], এখনো infinity থাকলে -1 """ INF = float("inf") dp = [INF] * (amount + 1) dp[0] = 0 for a in range(1, amount + 1): for c in coins: if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1 return dp[amount] if dp[amount] != INF else -1 # --------------------------------------------------------------------------- # 4. Grid paths (LeetCode 62 style) — grid DP, optional obstacle-সহ # --------------------------------------------------------------------------- def grid_paths(m, n, blocked=None): """(0,0) থেকে (m-1,n-1)-এ path গোনো, শুধু right বা down চলে। `blocked` হলো optional একটা set — যে (r, c) cell-গুলোতে ঢোকা যায় না (CSES Grid Paths-এর flavor)। STATE dp[r][c] = (0,0) থেকে (r,c) পর্যন্ত path-এর সংখ্যা TRANSITION dp[r][c] = dp[r-1][c] + dp[r][c-1]; blocked হলে 0 BASE dp[0][0] = 1 (blocked না হলে) FILL ORDER row by row, বাঁ থেকে ডানে (arrow তাক করে উপরে আর বাঁয়ে) ANSWER dp[m-1][n-1] """ blocked = blocked or set() dp = [[0] * n for _ in range(m)] for r in range(m): for c in range(n): if (r, c) in blocked: continue # 0-ই থেকে যায় if r == 0 and c == 0: dp[r][c] = 1 continue top = dp[r - 1][c] if r > 0 else 0 left = dp[r][c - 1] if c > 0 else 0 dp[r][c] = top + left return dp[m - 1][n - 1] # --------------------------------------------------------------------------- # 5. Longest increasing subsequence (LeetCode 300) — LIS family, O(n^2) # --------------------------------------------------------------------------- def lis_length(a): """Longest strictly increasing subsequence-এর length। STATE dp[i] = ঠিক index i-তে শেষ হওয়া longest increasing subsequence-এর length <- anchor-টা! TRANSITION dp[i] = 1 + max(dp[j]) — a[j] < a[i] এমন j < i-এর উপর (এমন j না থাকলে শুধু 1) BASE প্রতিটা dp[i] শুরু হয় 1 দিয়ে (element-টা একা) FILL ORDER i = 0 .. n-1 ANSWER max(dp) — dp[n-1] নয়; best-টা যেকোনো জায়গায় শেষ হতে পারে """ n = len(a) if n == 0: return 0 dp = [1] * n for i in range(n): for j in range(i): if a[j] < a[i] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 return max(dp) # --------------------------------------------------------------------------- # 6. 0/1 knapsack — knapsack family (প্রতিটা item সর্বোচ্চ একবার) # --------------------------------------------------------------------------- def knapsack_01(weights, values, capacity): """`capacity`-র মধ্যে item-গুলোর (প্রত্যেকটা একবার usable) max total value। STATE dp[w] = total weight <= w রেখে achievable best value, এ পর্যন্ত processed item-গুলো বিবেচনায় (2D dp[i][w]-টা এক row-তে compressed) TRANSITION dp[w] = max(dp[w], dp[w - wt] + val) BASE সব w-এর জন্য dp[w] = 0 (এখনো কোনো item নেই) FILL ORDER প্রতি item-এ, w sweep হয় ডান থেকে বাঁয়ে — এই direction-টাই "at most once" enforce করে; বাঁ-থেকে-ডান হলে item-টা reuse হয়ে নিঃশব্দে unbounded knapsack হয়ে যেত। ANSWER dp[capacity] """ dp = [0] * (capacity + 1) for wt, val in zip(weights, values): for w in range(capacity, wt - 1, -1): # ডান থেকে বাঁয়ে! if dp[w - wt] + val > dp[w]: dp[w] = dp[w - wt] + val return dp[capacity] # --------------------------------------------------------------------------- # Tests # --------------------------------------------------------------------------- def _tests(): # --- fib-এর তিন উপায় একমত ------------------------------------------- for n in range(15): assert fib_naive(n) == fib_memo(n) == fib_tab(n) assert fib_tab(50) == 12586269025 # বড় n memo/tab সহজে সামলায় assert fib_memo(50) == 12586269025 # --- climbing stairs ------------------------------------------------- assert climbing_stairs(1) == 1 assert climbing_stairs(2) == 2 # 1+1, 2 assert climbing_stairs(3) == 3 # 1+1+1, 1+2, 2+1 assert climbing_stairs(5) == 8 # ছদ্মবেশে Fibonacci assert climbing_stairs(10) == 89 # --- house robber ----------------------------------------------------- assert house_robber([]) == 0 assert house_robber([5]) == 5 assert house_robber([1, 2, 3, 1]) == 4 # বাড়ি 0 আর 2 লুট করো assert house_robber([2, 7, 9, 3, 1]) == 12 # 0, 2, 4 লুট করো assert house_robber([2, 1, 1, 2]) == 4 # দুই প্রান্ত লুট করো # --- coin change ------------------------------------------------------- assert coin_change([1, 2, 5], 11) == 3 # 5+5+1, walkthrough-টা assert coin_change([2], 3) == -1 # impossible assert coin_change([1], 0) == 0 # শূন্য বানাতে শূন্য coin assert coin_change([1, 3, 4], 6) == 2 # 3+3 — যেখানে greedy fail করে! # --- grid paths ---------------------------------------------------------- assert grid_paths(3, 3) == 6 # visual-explanation-এর grid-টা assert grid_paths(1, 1) == 1 assert grid_paths(3, 7) == 28 # LeetCode 62 sample-এর আকার assert grid_paths(3, 3, blocked={(1, 1)}) == 2 # মাঝখান ঘুরে যেতে বাধ্য assert grid_paths(2, 2, blocked={(0, 1), (1, 0)}) == 0 # দেয়াল-আটকানো # --- LIS --------------------------------------------------------------- assert lis_length([]) == 0 assert lis_length([7]) == 1 assert lis_length([10, 9, 2, 5, 3, 7, 101, 18]) == 4 # 2,3,7,18 (বা 101) assert lis_length([5, 4, 3, 2, 1]) == 1 # strictly decreasing assert lis_length([1, 3, 6, 7, 9, 4, 10, 5, 6]) == 6 # --- 0/1 knapsack ---------------------------------------------------------- assert knapsack_01([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9 # item w=3 + w=4 assert knapsack_01([2, 2, 2], [5, 5, 5], 4) == 10 # মাত্র দুটো আঁটে assert knapsack_01([10], [100], 5) == 0 # কিছুই আঁটে না assert knapsack_01([], [], 10) == 0 # "at most once" check: value 6-এর একটা item দুবার নেওয়া যাবে না assert knapsack_01([3], [6], 9) == 6 if __name__ == "__main__": _tests() # -------- markdown walkthrough-গুলোর ছোট্ট demo -------- print("fib(30): naive =", fib_naive(30), "| memo =", fib_memo(30), "| tab =", fib_tab(30)) print("climbing_stairs(5) =", climbing_stairs(5), " (expected 8)") print("house_robber([2,7,9,3,1]) =", house_robber([2, 7, 9, 3, 1]), " (expected 12)") print("coin_change([1,2,5], 11) =", coin_change([1, 2, 5], 11), " (expected 3: 5+5+1)") print("coin_change([1,3,4], 6) =", coin_change([1, 3, 4], 6), " (expected 2 — greedy would say 3)") print("grid_paths(3, 3) =", grid_paths(3, 3), " (expected 6)") print("lis_length([10,9,2,5,3,7,101,18]) =", lis_length([10, 9, 2, 5, 3, 7, 101, 18]), " (expected 4)") print("knapsack_01(w=[1,3,4,5], v=[1,4,5,7], cap=7) =", knapsack_01([1, 3, 4, 5], [1, 4, 5, 7], 7), " (expected 9)") print("All asserts passed.")