dynamic programming

Articles

GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Floyd–Warshall algorithm Shortest paths between all pairs of vertices in O(n³): dynamic programming over allowed transfers. O(n³) 2 problems GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 problems STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems DP Technique Interval DP The state is an interval [i, j], the transition is where to cut it: search trees, matrix chain order, sawing. O(n³) 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems DP Technique Digit DP Lucky tickets in any range in one pass over the digits: 55,252 out of a million, and any range up to 10¹⁸, in about a millisecond. O(D · 10 · S) 2 problems DP Technique Convex hull trick A minimum of lines instead of a search: 1776 catalogue tests split into sandbox runs, and a quadratic DP becomes linear. O(n) 2 problems DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems

Problems

Airports opening At most k exchanges Routes with no step back Sawing a log Sequencer errors A lift without fours An avalanche of retries Brackets on a calculator Exact change Lucky in a range One free ride The shortest loop Who takes which order Batches of tests Exam days Merge neighbours Reading evenings The goods lift The snowplough

Often together

contests 8 classic 7 optimization 5 interviews 4 graph 3 matrix 3 maps and navigation 3 bioinformatics 3 counting 3 shortest path 2 weighted graph 2 networks 2