Top DP Problems (LeetCode)

# DP Problems Pattern Map:
#
# PATTERN 1: Linear DP (Fibonacci-type)
# +-- 70. Climbing Stairs
# +-- 746. Min Cost Climbing Stairs
#
# PATTERN 2: 0/1 Knapsack
# +-- 322. Coin Change
# +-- 416. Partition Equal Subset Sum
#
# PATTERN 3: Subsequence DP
# +-- 300. Longest Increasing Subsequence
# +-- 139. Word Break
#
# PATTERN 4: 2D Grid DP
# +-- 62. Unique Paths
# +-- 120. Triangle (Min Path Sum variant)
#
# PATTERN 5: Interval DP
# +-- 152. Maximum Product Subarray
# +-- 64. Decode Ways

# 70. Climbing Stairs � Easy
# n stairs hain, 1 ya 2 steps le sakte ho
# Kitne tarike hain top pahunchne ke?

def climbStairs(n):
 if n <= 2:
 return n
 dp = [0] * (n + 1)
 dp[1], dp[2] = 1, 2
 for i in range(3, n + 1):
 dp[i] = dp[i - 1] + dp[i - 2]
 return dp[n]

# Pattern: Fibonacci
# dp[i] = dp[i-1] + dp[i-2]
# Time: O(n), Space: O(n) � optimize to O(1)

# 322. Coin Change � Medium
# coins diye hain, amount diya hai
# Minimum coins se amount banao

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

# Pattern: Unbounded Knapsack (coins unlimited)
# dp[i] = min coins to make amount i
# Time: O(amount * coins), Space: O(amount)

# 300. Longest Increasing Subsequence � Medium
# Array mein longest increasing subsequence nikalo

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

# Pattern: Linear DP with inner loop
# dp[i] = LIS ending at index i
# Time: O(n^2), Space: O(n)

# 139. Word Break � Medium
# String ko dictionary words mein break kar sakte ho?

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

# Pattern: Linear DP with dictionary check
# dp[i] = True if s[0:i] can be segmented
# Time: O(n^2 * k), Space: O(n)

# 152. Maximum Product Subarray � Medium
# Array mein maximum product subarray nikalo

def maxProduct(nums):
 result = max(nums)
 curMax, curMin = 1, 1
 for num in nums:
 vals = (num, num * curMax, num * curMin)
 curMax, curMin = max(vals), min(vals)
 result = max(result, curMax)
 return result

# Pattern: Track max AND min (negative � negative = positive)
# curMax = max(num, num*curMax, num*curMin)
# curMin = min(num, num*curMax, num*curMin)
# Time: O(n), Space: O(1)

# 91. Decode Ways � Medium
# "12" ? "AB" (1,2) ya "L" (12)
# Kitne tarike se decode kar sakte ho?

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

# Pattern: Fibonacci-type with conditions
# Single digit (1-9) ya double digit (10-26) decode ho sakta hai
# Time: O(n), Space: O(n)

# 62. Unique Paths � Medium
# m x n grid mein kitne unique paths hain?

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[m-1][n-1]

# Pattern: 2D Grid DP
# dp[i][j] = paths to reach cell (i,j)
# dp[i][j] = dp[i-1][j] + dp[i][j-1]
# Time: O(m*n), Space: O(m*n) � optimize to O(n)

# 746. Min Cost Climbing Stairs � Easy
# Har step pe cost hai, 1 ya 2 steps le sakte ho
# Minimum cost se top pahuncho

def minCostClimbingStairs(cost):
 n = len(cost)
 dp = [0] * (n + 1)
 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]

# Pattern: Linear DP with cost
# dp[i] = minimum cost to reach step i
# Ya toh i-1 se aao (cost[i-1] lagao)
# Ya toh i-2 se aao (cost[i-2] lagao)
# Time: O(n), Space: O(n)

# 416. Partition Equal Subset Sum � Medium
# Array ko 2 equal sum subsets mein divide kar sakte ho?

def canPartition(nums):
 total = sum(nums)
 if total % 2 != 0:
 return False
 target = total // 2
 dp = [False] * (target + 1)
 dp[0] = True
 for num in nums:
 for j in range(target, num - 1, -1):
 dp[j] = dp[j] or dp[j - num]
 return dp[target]

# Pattern: 0/1 Knapsack (subset sum variant)
# Total sum even hai toh half sum pe subset sum check karo
# Time: O(n * target), Space: O(target)

# 120. Triangle � Medium
# Triangle mein top se bottom jaao
# Minimum path sum nikalo

def minimumTotal(triangle):
 n = len(triangle)
 dp = triangle[-1][:] # Last row se shuru
 for i in range(n - 2, -1, -1):
 for j in range(i + 1):
 dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
 return dp[0]

# Pattern: 2D Grid DP (bottom-up)
# Har node ke liye: neeche left ya neeche right
# Bottom-up se shuru karo � space O(n)
# Time: O(n^2), Space: O(n)