Tabulation के साथ Bottom-Up DP

# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)

# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0] = 0  # base case
    dp[1] = 1  # base case
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Space-optimised to O(1):
def fib_optimised(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_optimised(50))  # 12586269025

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:  # can use this coin
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 5, 6, 9], 11))  # 2: (5+6)
print(coin_change([2], 3))             # -1: impossible
print(coin_change([1, 2, 5], 11))      # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249))  # 20

# Fill order examples:

# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n

# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.

# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems

print('Draw dependencies first, then determine fill order')

def lcs_bottom_up(s1, s2):
    m, n = len(s1), len(s2)
    # (m+1) x (n+1) table, initialised to 0
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:         # characters match
                dp[i][j] = 1 + dp[i-1][j-1]
            else:                            # skip one character
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

print(lcs_bottom_up('abcde', 'ace'))   # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB'))  # 4: 'BCAB' or 'BDAB'

def lcs_space_optimised(s1, s2):
    m, n = len(s1), len(s2)
    # Keep only one row (previous row state)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = 1 + prev[j-1]  # dp[i-1][j-1]
            else:
                curr[j] = max(prev[j], curr[j-1])  # dp[i-1][j] and dp[i][j-1]
        prev = curr
    return prev[n]

print(lcs_space_optimised('abcde', 'ace'))   # 3
# Space: O(n) instead of O(mn)

def rob_bottom_up(nums):
    if not nums: return 0
    if len(nums) == 1: return nums[0]

    # Full table version: O(n) space
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = 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]

def rob_optimised(nums):
    # O(1) space: only need last two values
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
    return prev1

print(rob_optimised([2, 7, 9, 3, 1]))  # 12

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    # Fill first row (can only come from left)
    for c in range(1, cols):
        dp[0][c] = dp[0][c-1] + grid[0][c]
    # Fill first column (can only come from above)
    for r in range(1, rows):
        dp[r][0] = dp[r-1][0] + grid[r][0]
    # Fill rest of the table
    for r in range(1, rows):
        for c in range(1, cols):
            dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
    return dp[rows-1][cols-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid))  # 7: 1+3+1+1+1

def min_path_sum_inplace(grid):
    rows, cols = len(grid), len(grid[0])
    # Modify grid in-place (O(1) extra space, destroys input)
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue  # starting cell
            elif r == 0:
                grid[r][c] += grid[r][c-1]  # first row
            elif c == 0:
                grid[r][c] += grid[r-1][c]  # first column
            else:
                grid[r][c] += min(grid[r-1][c], grid[r][c-1])
    return grid[rows-1][cols-1]

import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid)))  # 7

import functools

# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(rem):
        if rem == 0: return 0
        if rem < 0: return float('inf')
        return 1 + min(dp(rem - c) for c in coins)
    r = dp(amount)
    return r if r != float('inf') else -1

# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change_top([1,5,6,9], 11))    # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2

def unique_paths(m, n):
    # dp[i][j] = number of paths to reach cell (i,j)
    dp = [[1] * n for _ in range(m)]
    # Base: first row and first column are all 1
    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]

print(unique_paths(3, 7))   # 28
print(unique_paths(3, 2))   # 3

# O(n) space rolling row:
def unique_paths_opt(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j-1]
    return row[n-1]

print(unique_paths_opt(3, 7))  # 28