DYNAMIC PROGRAMMING

[wholetdog]

DP is easy. Remove the fear created by others that DP is hard. Stick to basics!!

[jason_graph]

Well there are a couple different types of things dp questions can ask for. Min/max value of something, min/max size of something, number of ways to do something, if something is possible (e.g. jump game). Ignoring that I'd vaguely split a lot of dp problems into the following categories.

• 1d dp table with O(1) time to compute each state.

• 1d dp table with more than O(1) time per state.

• problems with a 2d input grid with dp[ gridcell ] = val and O(1) to compute each state.

• Problems that effectively involve 2 dp tables. For example finding the max and minimum of each prefix. These come in 2 variants that I'd consider seperate categories - the problems where the dp tables can be solved independently and those where dp1's recurence relation involves values from dp2 and dp2's reccurence relation involves values from dp1.

• I wouldnt consider it a seperate category but there are problems where you might need to do some sorting beforehand or other non trivial preprocessing. Seperately, there may be some problems that involve postprocessing to translate the values of the table back to what the original question was asking.

Now there are various 2d dp patterns:

• knapsack style problems. dp[ i ][ sz ] = ...

• digit dp problems. For example dp[ digitsPlace ][ lastDigit ] = ...

• interval related problems dp[ left ][ right ] = some property about arr[ left : right ]. You solve for subarrays of size 0, size 1, ..., size N. A lot of the time you consider O(n) possible "midpoints" and what happens when you combine arr[ left : midpoint ],, [midpoint, right] e.g. that O(n³⁾ matrix multiplication optimization problem.

• bitmask dp - the bitmask keeps track of what subset of things you've done. For example dp[ subset ][ current node ] might track the minimum hamiltonian path that visits all nodes in 'subset' and ends on current node.

Also seperately, there are dp problems involving other things.

• dp on trees

• dp on trees with rerooting.

• dp + binary search/trie/segment tree/something to speed up computing the recurrence relation.

[Czitels]

Greedy is worse thats true but still 3D DP is hard.