Problem link ও উৎস
- **Original source:** Classic 1D minimization DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Easy
- **Pattern:** 1D linear DP (min)
- **Basic idea inherited from:** #2 Climbing Stairs — `+` কে `min` দিয়ে বদলে দাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
প্রতিটা সিঁড়ির ধাপে একটা cost লেখা আছে — array `cost`। তুমি index 0 বা index 1 থেকে শুরু করতে পারো। কোনো ধাপ থেকে 1 বা 2 ধাপ এগোতে পারো, আর যে ধাপ থেকে এগোও তার cost দিতে হয়। সবচেয়ে কম মোট cost-এ চূড়ায় (শেষ ধাপের ঠিক পরের জায়গায়) পৌঁছাও।
```text
cost = [10, 15, 20]
সবচেয়ে সস্তা: index 1 থেকে শুরু (start free), cost 15 দিয়ে দুই ধাপ লাফিয়ে চূড়ায় -> মোট 15
(index 0 থেকে শুরু করলে: cost 10, তারপর index 2-এর cost 20 = 30 — বেশি)
```
### Input ও output {#8-example-input-and-output}
```text
Input : cost = [10, 15, 20] -> Output: 15
Input : cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] -> Output: 6
Edge case 1: cost = [0, 0] -> Output: 0
Edge case 2: cost = [5, 10] -> Output: 5 (index 0 থেকে এক লাফ, cost 5; index 1 থেকে হলে 10)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতিটা সিঁড়ির ধাপে পা রাখলে একটা টোল দিতে হয়। তুমি চাও সবচেয়ে কম টোলে উপরে উঠতে। প্রতিটা জায়গায় দাঁড়িয়ে জিজ্ঞেস করো: "এখানে এলাম কোথা থেকে — ঠিক নিচের ধাপ থেকে এক পা, নাকি তার নিচের থেকে দুই পা? কোনটায় এ পর্যন্ত মোট টোল কম?" সেই সস্তা পথটাই বেছে নাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা #2 Climbing Stairs-এর সরাসরি বিবর্তন। সেখানে আমরা **ways যোগ** করতাম (`+`); এখানে আমরা **সবচেয়ে সস্তা route খুঁজি**, তাই `+`-এর জায়গায় `min` বসে। Structure (পেছনের দুই ঘরে তাকানো) একই থাকে — শুধু operation বদলায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: কোনো position-এ পৌঁছানোর সবচেয়ে সস্তা উপায় = (আগের ধাপ থেকে এক লাফে আসার খরচ) আর (দুই আগের ধাপ থেকে দুই লাফে আসার খরচ) — এর মধ্যে যেটা ছোট। যেহেতু shortest/cheapest path-এর টুকরোও cheapest (optimal substructure), আমরা ছোট subproblem-এর min থেকে বড়টার min বানাতে পারি।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **array** `dp` (size `n+1`, যেখানে `n = len(cost)`), `dp[i]` = position `i`-তে পৌঁছানোর min cost। অথবা শুধু **দুটো variable**, যেহেতু dependency পেছনের দুই ঘরে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State এখানে একটামাত্র সংখ্যা: তুমি কোন position-এ। তাই index দিয়ে চলা flat array নিখুঁত — `dp[i]` position `i`-এর min cost ধরে। চূড়াটাকে index `n` ভাবলে (শেষ ধাপের পরের জায়গা) উত্তরটা সরাসরি `dp[n]`-এ পাওয়া যায়। Dependency দুই ঘরে, তাই দুই variable-এ সঙ্কুচিত হয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: চূড়া থেকে পেছন দিকে recurse করো — চূড়ায় ঢুকতে শেষ লাফটা কোথা থেকে, সেই সব সম্ভাবনার min নাও।
```text
min_cost(i): # position i-তে পৌঁছানোর min cost
if i <= 1: return 0 # 0 বা 1 থেকে free start
return min( min_cost(i-1) + cost[i-1],
min_cost(i-2) + cost[i-2] )
answer = min_cost(n)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **O(2^n)** — প্রতিটা call দুটো ছোট call করে, আর একই position বারবার গোনা হয় (overlapping subproblems)। `min_cost(i-1)` আর `min_cost(i-2)` দুজনেই নিচে গিয়ে আবার একই subproblem ছোঁয়। n বড় হলে exponential blow-up।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা position-এর min cost একবারই গোনা দরকার**, কারণ সেটা শুধু পেছনের দুই position-এর min cost-এর উপর নির্ভর করে। একবার গুনে রেখে দিলে exponential কাজ linear হয়ে যায় — Climbing Stairs-এর মতোই, শুধু `+`-এর জায়গায় `min`।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i]` = position `i`-তে পৌঁছানোর minimum মোট cost (যেখানে position `n` = চূড়া)।
**Transition:**
```text
dp[i] = min( dp[i-1] + cost[i-1], # ঠিক নিচের ধাপ থেকে এক লাফ
dp[i-2] + cost[i-2] ) # তার নিচের থেকে দুই লাফ
```
**Base case:** `dp[0] = 0`, `dp[1] = 0` (index 0 বা 1 — দুটোই free starting point)।
**Answer location:** `dp[n]`, যেখানে `n = len(cost)`।
Memoization (top-down): উপরের `min_cost(i)` recursion-টাই রাখো, dict যোগ করো। Tabulation (bottom-up): `dp[0]=dp[1]=0` থেকে শুরু করে ছোট-থেকে-বড় ভরো। যেহেতু শুধু পেছনের দুই cell লাগে, দুই variable rolling করে O(1) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** Climbing Stairs-এর "কতভাবে?" থেকে এখানে "সবচেয়ে সস্তা কত?" — শুধু এই পরিবর্তনটুকু বুঝলে operation নিজে নিজেই বদলে যায়: যোগ (`+`) হয়ে যায় min, base case 1 হয়ে যায় 0। একই কঙ্কাল, ভিন্ন মাংস। DP-তে বহু problem এভাবে একে অপরের রূপান্তর।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[i]` = position `i`-তে পৌঁছানোর min cost। `cost = [10, 15, 20]`, তাই চূড়া = index 3:
```text
cost : 10 15 20 (top)
index : 0 1 2 3
dp[0] = 0 (free start, index 0-তে শুরু)
dp[1] = 0 (free start, index 1-তে শুরু)
dp[2] = min( dp[1] + cost[1], dp[0] + cost[0] )
= min( 0 + 15, 0 + 10 ) = 10
dp[3] = min( dp[2] + cost[2], dp[1] + cost[1] )
= min( 10 + 20, 0 + 15 ) = 15 <- answer
index : 0 1 2 3
dp : 0 0 10 15
```
প্রতিটা ঘর পেছনের দুই ঘর + সেখানকার cost-এর মধ্যে min নেয়।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]`, n = 10, tabulation:
1. `dp[0] = 0`, `dp[1] = 0`
2. dp[2] = min(0+100, 0+1) = 1
3. dp[3] = min(1+1, 0+100) = 2
4. dp[4] = min(2+1, 1+1) = 2
5. dp[5] = min(2+1, 2+1) = 3
6. dp[6] = min(3+100, 2+1) = 3
7. dp[7] = min(3+1, 3+100) = 4
8. dp[8] = min(4+1, 3+1) = 4
9. dp[9] = min(4+100, 4+1) = 5
10. dp[10] = min(5+1, 4+100) = 6 → answer
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def min_cost_memo(cost):
n = len(cost)
memo = {}
def solve(i): # position i-তে পৌঁছানোর min cost
if i <= 1:
return 0 # free start at 0 or 1
if i in memo:
return memo[i]
memo[i] = min(solve(i - 1) + cost[i - 1],
solve(i - 2) + cost[i - 2])
return memo[i]
return solve(n)
# ---- way 2: tabulation (bottom-up) ----
def min_cost_tab(cost):
n = len(cost)
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 0 # base cases
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1],
dp[i - 2] + cost[i - 2])
return dp[n]
# ---- way 3: O(1) space ----
def min_cost_fast(cost):
a, b = 0, 0 # dp[i-2], dp[i-1]
for i in range(2, len(cost) + 1):
a, b = b, min(b + cost[i - 1], a + cost[i - 2])
return b
# ---- tests ----
cases = [
([10, 15, 20], 15),
([1, 100, 1, 1, 1, 100, 1, 1, 100, 1], 6),
([0, 0], 0),
([5, 10], 5),
([1, 2], 1),
]
for cost, want in cases:
assert min_cost_memo(cost) == want, (cost, min_cost_memo(cost))
assert min_cost_tab(cost) == want, (cost, min_cost_tab(cost))
assert min_cost_fast(cost) == want, (cost, min_cost_fast(cost))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `min_cost_memo`: ভেতরের `solve(i)` position `i`-তে পৌঁছানোর min cost দেয়; `i <= 1` free; `memo` repeated কাজ এড়ায়।
- `min_cost_tab`: `dp[0]=dp[1]=0` base; loop পেছনের দুই cell + সেখানকার cost-এর min নেয়; answer `dp[n]`।
- `min_cost_fast`: `a` = `dp[i-2]`, `b` = `dp[i-1]`; এক assignment-এই দুজনে এক ধাপ এগোয়, পুরো array লাগে না।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ পাঁচটা input আর তাদের সঠিক উত্তর আছে — LeetCode-এর দুটো example, দুটো ছোট edge case, আর একটা two-element case। প্রতিটার জন্য তিনটা function-ই মিলতে হবে। সব assert pass হলে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
তিন version-ই **O(n)** — প্রতিটা position একবার করে গোনা হয়। (Naive recursion ছিল O(2^n)।)
### অতিরিক্ত জায়গা {#19-space-complexity}
- Memoization: **O(n)** — dict + recursion stack।
- Tabulation: **O(n)** — `dp` array।
- Fast version: **O(1)** — দুটো variable।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- চূড়াকে index `n` না ধরে `n-1` ভাবা — তখন শেষ ধাপের cost অযথা যোগ হয়; চূড়া হলো শেষ ধাপের ঠিক **পরের** জায়গা।
- cost যোগের সময় ভুল index — `dp[i-1] + cost[i]` লেখা; ঠিকটা `dp[i-1] + cost[i-1]` (যে ধাপ ছাড়ছি তার cost)।
- base case `dp[0], dp[1]` কে 0-র বদলে `cost[0], cost[1]` ভাবা — শুরুর position নিজে free, তাই 0; cost লাগে শুধু ধাপ **ছাড়ার** সময়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: #2 Climbing Stairs-এর পেছন-দুই-ঘর structure, `+` কে `min` দিয়ে বদলানো। [../state-transition-thinking.md](../state-transition-thinking.md)-এর min-vs-count আলোচনা আর tracker-এর "minimizing শুরু হয় dp[0]=0 দিয়ে" নিয়ম এখানে সরাসরি লাগে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Coin Change (min coins, unbounded) —