In a nutshell
The travelling salesman problem asks for the cheapest route that visits every city once and returns home. Held-Karp avoids checking all n! tours by noticing that two partial routes covering the same cities and ending at the same one have identical futures — so it stores the best cost per (visited-set, endpoint) and reuses it, cutting the work to about 2ⁿ·n².