# Dynamic Programming

• USACO Number Triangles
• Find maximum sum from root to leaf in a tree.
• USACO Subset Sums
• Find number of possible subsets adding to a number.
• Typical knapsack.
• USACO Longest Prefix
• Find the longest prefix of a string constructable by words from a dictionary.
• Use Trie with DP.
• USACO Cow Pedigrees
• Find number of possible complete binary trees with N nodes.
• Catalan number.
• USACO Money Systems
• Find number of ways to compose N given smaller numbers M1, M2, …, Mi.
• Typical complete knapsack.
• USACO Score Inflation
• 0/1 knapsack.
• USACO Stamps
• Find minimum number that cannot be summed to by at most K numbers drawn from a set.
• DP on minimum number of solution summed to M with first N numbers.
• USACO Stringsobits
• Find the k-th largest number having no more than N 1-bits.
• DP on number of N-length no more than M-1-bit numbers.
• USACO Shopping Offers
• Find the minimum cost to satisify a target combination with given combinations.
• Multiple dimension knapsack.
• USACO Home on the Range
• Find all squares in an area with obstacles.
• DP on maximum square edge size.
• USACO Raucous Rockers
• Store maximum number of songs in CDs with chronological order. (Brute force will also do though)
• DP on F[M][N][T], maximum of songs can put with first M songs, first N CD’s and last CD remaining time T.
• USACO Beef McNuggets
• Find minimum number that cannot be summed to by a set of numbers. Number usage is not limited.
• Extended euclid: ax + by = gcd(a, b). If gcd > 1, then no limit. If smallest number == 1, then all ok. Else, use method in Stamps. Exit once the following 256 bits are all 1.
• Find number of unique longest decreasing subsequences.
• Find maximum length, then count unique ones. For i < j, if maxLen[i] + 1 == maxLen[j], then uniqNums[j] = uniqNums[i] if nums[i] == nums[j], uniqNums[j] = uniqNums[i] + uniqNums[j] if nums[i] < nums[j].
• USACO Milk Measuring
• Given a set of numbers and a target, find minimum subset, numbers drawn from which summed to the target.
• DFSID + DP validation also works.
• USACO Big Barn
• Find maximum square in an area with obstacles.
• USACO Canada Tour
• Hamilton circle on a straight line.
• F[m][n]: max city number from m -> start -> n. m is always <= n.
• USACO Character Recognition
• F[m] = min(F[m - 19] + cost(missing), F[m - 20] + cost(normal), F[m - 21] + cost(duplicate))
• USACO Two Five
• Very good question! See answer and solution on USACO for more details.
• POJ 1837 Balance
• Given a balance and weights and loadable positions, find number of balanced configurations.
• State: F[M][N], number of ways by which load N can be reached by first M weights.
• POJ 1276 Cash Machine
• 0/1 Knapsack with object number limit.
• Need binary optimization (2^0, 2^1, …, 2^k, N-(1+…+2^k)), where k is the maximum i.e. N-(…)>=0.
• POJ 2151 Check the difficulty of problems
• Probability DP. Given probability list, F[m][n]: probability of selecting n from m.

# Graph

• Shortest Path
• Bellman-Ford
• Dijkstra
• Floyd
• SPFA
• USACO Bessie Come Home
• Floyd.
• USACO Cow Tours
• Given un-connected regions, find minimum diameter of graph formed by connecting any two of them.
• Floyd and enumerate connected point pairs.
• USACO Sweet Butter
• Heap-optimized Dijkstra.
• USACO Camelot
• SPFA (BFS without visited), for each knight calculate minimum cost to all grids with or w/o king. Note that “no king” can go to “with king”, but not vice versa.
• USACO Fence Loops
• Find shortest cycle in a weighted graph.
• For each edge break it and do dijkstra.
• POJ 1860 Currency Exchange
• Find exchange rate > 1 in the exchange grph, from given currency. Bellman-ford.
• POJ 3259 Wormholes
• Find negative circle in the whole graph. Floyd.
• POJ 1062 昂贵的聘礼
• Define “having nothing” state HN. For each gift G valued p, we have (HN, G) edge with cost p. For each replacement G’ with better price q, we have (G’, G) with cost q. Do shortest path with Dijkstra.
• POJ 2253 Frogger
• For each point, find minimum of max edge length of path to it. Dijkstra, change objective to minimize edge length. Greedy policy can be prooved.
• POJ 1125 Stockbroker Grapevine
• Bare floyd.
• POJ 2240 Arbitrage
• Similar to 1860, but consider all start currency. Floyd.
• Topological Sort
• Eularian Path
• Minimum Spanning Tree
• Network Flow
• Max-Flow
• Edmond-Karp
• USACO Drainage Ditches
• Bare Edmond-Karp.
• USACO Pollutant Control
• Find minimum edge cut with minimum edge number.
• To minimize the edge number, solve minimum cut among full-capacity edges. Full edges are refilled with weight 1, others with infinity. As a result, max-flow capacity == min-cut capacity == min edge number.
• USACO TeleCowmunication
• Minimum node cut.
• POJ 1459 Power Network
• Given power plants, consumers and dispatchers, find maximum power consumed.
• Bare max flow. Connect plants to source and consumers to sink.
• Maximum Matching
• Bi-Partite Graph
• Hungarian
• POJ 3041 Asteroids
• Given (x, y) points, one can eliminate a row or a col. Find minimum steps to eliminate all points.
• Build x-y bi-partite graph with super source and sink, find minimum cut (maximum match). Graph cut means no more points.
•  There is a Konig theorem: min-node-cov = max-match .
• POJ 3020 Antenna Placement
• Given (x, y) points, one can cover points using length-2 capsules. Find minimum capsules needed.
•  nodes = max-match + min-edge-cov . Positions as nodes, capsules as edges.
• Flood Filling
• Strong Connected Region