003 — Min Cost Climbing Stairs

Source

• Original source: Classic 1D minimization DP exercise
• Platform: LeetCode — https://leetcode.com/problems/min-cost-climbing-stairs/
• Topic: dynamic programming
• Difficulty: Easy
• Pattern: 1D linear DP (min)
• Basic idea inherited from: #2 Climbing Stairs — + কে min দিয়ে বদলে দাও

1. Problem in simple words

প্রতিটা সিঁড়ির ধাপে একটা cost লেখা আছে — array cost। তুমি index 0 বা index 1 থেকে শুরু করতে পারো। কোনো ধাপ থেকে 1 বা 2 ধাপ এগোতে পারো, আর যে ধাপ থেকে এগোও তার cost দিতে হয়। সবচেয়ে কম মোট cost-এ চূড়ায় (শেষ ধাপের ঠিক পরের জায়গায়) পৌঁছাও।

cost = [10, 15, 20]
সবচেয়ে সস্তা: index 1 থেকে শুরু (start free), cost 15 দিয়ে দুই ধাপ লাফিয়ে চূড়ায় -> মোট 15
(index 0 থেকে শুরু করলে: cost 10, তারপর index 2-এর cost 20 = 30 — বেশি)

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-এ সঙ্কুচিত হয়।

6. Real-life analogy

ভাবো প্রতিটা সিঁড়ির ধাপে পা রাখলে একটা টোল দিতে হয়। তুমি চাও সবচেয়ে কম টোলে উপরে উঠতে। প্রতিটা জায়গায় দাঁড়িয়ে জিজ্ঞেস করো: "এখানে এলাম কোথা থেকে — ঠিক নিচের ধাপ থেকে এক পা, নাকি তার নিচের থেকে দুই পা? কোনটায় এ পর্যন্ত মোট টোল কম?" সেই সস্তা পথটাই বেছে নাও।

7. Visual explanation

dp[i] = position i-তে পৌঁছানোর min cost। cost = [10, 15, 20], তাই চূড়া = index 3:

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 নেয়।

8. Example input and output

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)

9. Brute force thinking

প্রথম সরল চিন্তা: চূড়া থেকে পেছন দিকে recurse করো — চূড়ায় ঢুকতে শেষ লাফটা কোথা থেকে, সেই সব সম্ভাবনার min নাও।

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:

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 এভাবে একে অপরের রূপান্তর।

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

15. Python solution

# ---- 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 লাগে না।

17. Output walkthrough

cases-এ পাঁচটা input আর তাদের সঠিক উত্তর আছে — LeetCode-এর দুটো example, দুটো ছোট edge case, আর একটা two-element case। প্রতিটার জন্য তিনটা function-ই মিলতে হবে। সব assert pass হলে শেষে print: সব test pass!।

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 লাগে শুধু ধাপ ছাড়ার সময়।

21. Which basic problem this inherits from

ভিত্তি: #2 Climbing Stairs-এর পেছন-দুই-ঘর structure, + কে min দিয়ে বদলানো। ../state-transition-thinking.md-এর min-vs-count আলোচনা আর tracker-এর "minimizing শুরু হয় dp[0]=0 দিয়ে" নিয়ম এখানে সরাসরি লাগে।

22. Similar harder problems

• Coin Change (min coins, unbounded) — https://leetcode.com/problems/coin-change/ (এই tracker-এর #10)
• Minimum Path Sum (grid-এ min cost) — https://leetcode.com/problems/minimum-path-sum/ (#9)
• House Robber (take-or-skip, max version) — https://leetcode.com/problems/house-robber/ (#6)

23. Pattern learned

1D minimization DP: counting DP-র + কে min দিয়ে বদলাও, base case 1 কে 0 দিয়ে। Structure এক, লক্ষ্য আলাদা। এই "operation swap" reflex বহু DP-তে count ↔ min/max-এর মধ্যে দ্রুত যাওয়ার চাবি।

24. Final summary

ভবিষ্যতের আমাকে: "Min Cost Climbing = Climbing Stairs, কিন্তু + এর জায়গায় min, base 0।" State 'position i-তে পৌঁছানোর min cost', transition dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])। মনে রেখো: counting আর minimizing DP প্রায়ই একই কঙ্কাল — operation আর base case-টাই শুধু বদলায়।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।