Advanced Dynamic Programming

0/1 Knapsack

हर item के लिए, उसे लेना या छोड़ना तय करें। dp[w], capacity w से मिलने वाला सबसे अच्छा value रखता है; weight को उल्टा iterate करें ताकि हर item अधिकतम एक बार इस्तेमाल हो।

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[capacity]

Output:

knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)  # 9

Longest Common Subsequence

dp[i][j], text1[:i] और text2[:j] की LCS लंबाई है। मिलते characters diagonal को बढ़ाते हैं; वरना दोनों में से किसी एक string से एक character छोड़ने में जो बेहतर हो वह लें।

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Output:

lcs('abcde', 'ace')  # 3 ('ace')

Longest Increasing Subsequence

O(n^2) version हर पिछले index को आज़माता है। तेज़ O(n log n) version हर subsequence length के लिए सबसे छोटी tail का tails array रखता है, हर नए number को रखने के लिए binary search का उपयोग करते हुए।

import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Output:

length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])  # 4  ([2,3,7,101] etc.)

आकार पहचानें

दो strings/sequences और तुलना → LCS-जैसा 2D DP। एक ही sequence में 'बढ़ता/घटता' → LIS-जैसा। Capacity सीमा के साथ items का समूह → knapsack-जैसा।