LCS, LIS, knapsack ve subset DP

LCS'de dp[i][j], iki prefix'in en uzun ortak alt dizisinin boyudur. Son karakter eşitse diagonal+1; değilse üst/sol maksimumu. Subsequence bitişik olmak zorunda değildir; substring başka problemdir. Edit distance insert/delete/replace maliyetlerini son karara göre kurar.

0/1 knapsack tek boyuta sıkıştırıldığında capacity ters yönde gezilir; ileri gezmek aynı öğeyi birçok kez kullanıp unbounded varyanta dönüşebilir. LIS için tails[i], i+1 uzunluktaki artan alt dizinin mümkün en küçük son değeridir. tails listesi gerçek LIS olmak zorunda değildir; parent indeksleri reconstruction sağlar.

Subset DP state'i bir bitmask ve son düğümle tanımlar. TSP dp[mask][last] her visited subset için optimum maliyeti tutar. Tree DP çocukları birleştirir; DAG DP topological sıra kullanır. DP optimizasyonları (divide-and-conquer optimization, Knuth, convex hull trick) belirli monotonluk/convexity koşulları ister; her recurrence'a uygulanamaz.

from bisect import bisect_left

def lis_length(a):
    tails=[]
    for x in a:
        i=bisect_left(tails,x)
        if i == len(tails): tails.append(x)
        else: tails[i]=x
    return len(tails)
assert lis_length([3,1,2,5,4]) == 3
assert lis_length([2,2,2]) == 1