Poridhi: Dynamic Programming

Dynamic Programming related problems:

This blog post presents Python solutions to six classic dynamic programming problems that frequently appear in coding interviews and competitive programming. These problems include strategies for maximizing profit without choosing adjacent houses in House Robber, decoding numeric strings into alphabetic representations in Decode Ways, and counting unique paths in a grid in Unique Paths. It also covers determining reachability in an array using jumps in Jump Game, finding the longest increasing subsequence in a list of numbers in Longest Increasing Subsequence, and checking if a string can be segmented into dictionary words in Word Break. Each solution is designed using efficient DP techniques such as tabulation and memorization, helping readers understand the core ideas behind dynamic problem-solving in Python.

✅ House Robber

def rob(nums):
    if not nums: return 0
    if len(nums) <= 2: return max(nums)
    
    dp = [0] * len(nums)
    dp[0], dp[1] = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    
    return dp[-1]

---

✅ Decode Ways

def numDecodings(s):
    if not s or s[0] == '0': return 0
    
    dp = [0] * (len(s) + 1)
    dp[0], dp[1] = 1, 1
    
    for i in range(2, len(s) + 1):
        one = int(s[i-1:i])
        two = int(s[i-2:i])
        if 1 <= one <= 9:
            dp[i] += dp[i-1]
        if 10 <= two <= 26:
            dp[i] += dp[i-2]
    
    return dp[len(s)]

---

✅ Unique Paths

def uniquePaths(m, n):
    dp = [[1]*n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[-1][-1]

---

✅ Jump Game

def canJump(nums):
    goal = len(nums) - 1
    
    for i in range(len(nums)-2, -1, -1):
        if i + nums[i] >= goal:
            goal = i
            
    return goal == 0

---

✅ Longest Increasing Subsequence

def lengthOfLIS(nums):
    dp = [1] * len(nums)
    
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
    
    return max(dp)

---

✅ Word Break

def wordBreak(s, wordDict):
    wordSet = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    
    for i in range(1, len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break
                
    return dp[len(s)]