Dynamic Programming: 0/1 Knapsack, LCS & LIS

Dynamic programming is applicable when a problem has two key ingredients:

1. Optimal Substructure: An optimal solution to the problem contains within it optimal solutions to subproblems.

2. Overlapping Subproblems: A recursive algorithm visits the same subproblems repeatedly rather than generating new subproblems.

Top-Down (Memoization) vs Bottom-Up (Tabulation):

- Top-Down: Write natural recursive formulation, store computed results in hash table or array.

- Bottom-Up: Identify topological ordering of subproblem dependencies and fill an iterative DP table from base cases up.

0/1 Knapsack Recurrence:

DP[i][w] = DP[i-1][w] (if wt[i] > w), and max(DP[i-1][w], val[i] + DP[i-1][w - wt[i]]) (if wt[i] <= w).

Time complexity is O(n * W). This is pseudo-polynomial because the input length of capacity W is k = lceil log_2 W rceil bits. Thus W = 2^k, meaning the running time is exponential in the input representation size.

Longest Increasing Subsequence (LIS) in O(n log n):

Maintain an array tails where tails[len] stores the smallest tail of all increasing subsequences of length len + 1 found so far.

For each element x in A:

- Binary search for the first element in tails >= x.

- If found, replace it with x (maintaining smaller tail for that length).

- If x is larger than all elements in tails, append x to tails.

The length of tails at the end is the length of the LIS.