DP on Strings & Grids

# Longest Palindromic Substring — DP approach
def longestPalindrome(s):
 n = len(s)
 dp = [[False] * n for _ in range(n)]
 start, max_len = 0, 1
 
 # Single characters are palindromes
 for i in range(n):
 dp[i][i] = True
 
 # Check for length 2
 for i in range(n - 1):
 if s[i] == s[i + 1]:
 dp[i][i + 1] = True
 start, max_len = i, 2
 
 # Check for length 3+
 for length in range(3, n + 1):
 for i in range(n - length + 1):
 j = i + length - 1
 if s[i] == s[j] and dp[i + 1][j - 1]:
 dp[i][j] = True
 if length > max_len:
 start, max_len = i, length
 
 return s[start:start + max_len]

# Example
s = "babad"
print(f"Longest Palindrome: {longestPalindrome(s)}") # "bab" ya "aba"

# Word Break — kya string ko words mein break kar sakte ho?
def wordBreak(s, wordDict):
 n = len(s)
 dp = [False] * (n + 1)
 dp[0] = True # Empty string always breakable
 
 for i in range(1, n + 1):
 for word in wordDict:
 if len(word) <= i and s[i - len(word):i] == word:
 if dp[i - len(word)]:
 dp[i] = True
 break
 
 return dp[n]

# Example
s = "leetcode"
wordDict = ["leet", "code"]
print(f"Word Break possible: {wordBreak(s, wordDict)}") # True

# DP Table:
# s = "leetcode"
# dp[0] = True (empty)
# dp[4] = True ("leet" mila, dp[0] True)
# dp[8] = True ("code" mila, dp[4] True)

# Unique Paths — m x n grid
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]

# Grid Visualization (3x3):
# 1 1 1
# 1 2 3
# 1 3 6
#
# dp[0][*] = 1 (sirf right ja sakte ho)
# dp[*][0] = 1 (sirf down ja sakte ho)
# dp[i][j] = upar se aao + baayan se aao

# Grid Path Finding — 4x5 grid
#
# Col: 0 1 2 3 4
# Row:
# 0 1 1 1 1 1
# 1 1 2 3 4 5
# 2 1 3 6 10 15
# 3 1 4 10 20 35
#
# Har cell = upar ka + baayan ka
# dp[i][j] = dp[i-1][j] + dp[i][j-1]
#
# Path example: (0,0) — (0,1) — (1,1) — (1,2) — (2,2) — (2,3) — (2,4)
# Right, Down, Right, Down, Right, Down = 6 steps total

# Minimum Path Sum
def minPathSum(grid):
 m, n = len(grid), len(grid[0])
 dp = [[0] * n for _ in range(m)]
 dp[0][0] = grid[0][0]
 
 # First row — sirf baayan se aa sakte ho
 for j in range(1, n):
 dp[0][j] = dp[0][j - 1] + grid[0][j]
 
 # First column — sirf upar se aa sakte ho
 for i in range(1, m):
 dp[i][0] = dp[i - 1][0] + grid[i][0]
 
 # Baaki cells — min(upar, baayan) + current cost
 for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
 
 return dp[m - 1][n - 1]

# Example
grid = [
 [1, 3, 1],
 [1, 5, 1],
 [4, 2, 1]
]
print(f"Minimum Path Sum: {minPathSum(grid)}") # 7 (1?3?1?1?1)