Dynamic Programming in Hindi (Hinglish): Free Course

Hindi mein samjho (Hinglish)

Neeche is topic ka Hinglish explanation hai, wahi jo hamare course lesson mein audio narration ke saath chalta hai. Code English mein hai, samjhana Hindi mein.

Climbing Stairs

Climbing Stairs dynamic programming ka sabse friendly introduction hai. Problem ek math puzzle jaisa lagta hai. Solution ek line ka recursion hai jo exponentially slow nikalta hai. Iss slowness ko fix karna hi pura dynamic programming ka art hai, aur tum aaj poori four-stage progression seekhoge.

Pattern recognition. Step n tak pohochne ke tarike equal hain step n minus 1 ke tarike plus step n minus 2 ke tarike. Kyun? Kyunki tumhara last move ya toh n minus 1 se ek-step tha, ya n minus 2 se do-step. Wo recurrence hai f of n equals f of n minus 1 plus f of n minus 2. Yeh Fibonacci hai.

Python solution: Climbing Stairs

def climb(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Complexity: Naive recursion: time O(2ⁿ), space O(n); Memoized recursion (top-down DP): time O(n), space O(n); Constant-space DP: time O(n), space O(1).

House Robber

House Robber pehla dynamic programming problem hai jahan har step pe tumhe sach mein ek decision lena padta hai: yeh house lo, ya skip karo. Bas yeh ek twist tumhe Fibonacci-style DP se asli decision DP tak promote kar deta hai. Aaj recurrence sahi pakad lo, toh aage ke das DP problems same theme ke variations lagenge.

Pattern recognition. Jab bhi tum dekho "ek subset choose karo maximize ya minimize karne ke liye, aur constraint ho ki do chosen items kisi order mein adjacent nahi ho sakte": yeh take-or-skip DP pattern hai. Har index pe tumhare paas exactly do options hain: yeh lo aur do aage jaao, ya skip karo aur ek aage badho. Optimal sub-structure free mein mil jaata hai.

Asli unlock. dp of i define karo as maximum money jo tum rob kar sakte ho sirf houses zero se i tak consider karke. i pe decision binary hai, ya toh house i skip karo, toh dp of i equals dp of i minus 1, ya house i rob karo, toh i minus 1 rob nahi kiya hoga, toh dp of i equals dp of i minus 2 plus nums of i. Dono ka max lo. Bas yahi pura algorithm hai.

Python solution: House Robber

def rob(nums):
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

Complexity: Brute force (binary recursion): time O(2ⁿ), space O(n); Optimal DP (rolling variables): time O(n), space O(1).

Coin Change

Coin Change wo problem hai jahan greedy intuition tumhe dhokha de deta hai aur dynamic programming bachata hai. Tum yahaan unbounded knapsack template seekhoge, aur fir wahi shape Perfect Squares, Word Break, aur Combination Sum IV mein pehchaan loge. Iss ek ko master karo aur DP catalogue ki ek poori branch khul jaati hai.

Pattern recognition. Yeh unbounded knapsack hai ek dimension ke saath. State hai wo amount jo tum banana chahte ho. Transition poochta hai: last coin kaunsa daala? Har coin c ke liye, answer hai ek plus minimum coins for amount minus c. Saare coins pe min lo. Bas yahi pura algorithm hai.

Asli unlock. Ek one-dimensional DP table banao. dp of a matlab amount a banane ke liye minimum coins. Sab entries infinity se initialize karo, fir dp of zero ko zero set karo. Ab a ko ek se upar tak sweep karo. Har a ke liye, har coin c try karo. Agar a minus c non-negative hai, to dp of a equals dp of a minus c plus one ban sakta hai. Saare valid coins pe minimum lo. Last mein dp of amount return karo, ya agar abhi bhi infinity hai to minus one.

Python solution: Coin Change

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if a - c >= 0:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Complexity: Brute force recursion: time O(c^a) where c = #coins, a = amount, space O(a) recursion depth; Brute force recursion (no memo): time O(c^a), space O(a) recursion stack; Bottom-up DP (this lesson): time O(amount × len(coins)), space O(amount).