Visit all 4 cities once, starting and ending at A, as cheaply as possible. The state is the set of cities visited so far, and a set of 4 cities is an 4-bit number: bit 0 is A, bit 1 is B, and so on, written here with A on the right. Each row is one set, each column the city the path ends at, and the cell is the cheapest path from A through exactly that set ending there. Only sets containing A matter, so 8 rows instead of 16.
Bitmask dynamic programming for the travelling salesman over 4 cities.
Set 0011 = {A, B}, ending at B. The path arrived from the set without B, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 10 = 10.
dp of 0011 ending at B is 10.
Set 0101 = {A, C}, ending at C. The path arrived from the set without C, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 15 = 15.
dp of 0101 ending at C is 15.
Set 0111 = {A, B, C}, ending at B. The path arrived from the set without B, 0101 = {A, C}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is C: 15 + 35 = 50.
dp of 0111 ending at B is 50.
Set 0111 = {A, B, C}, ending at C. The path arrived from the set without C, 0011 = {A, B}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is B: 10 + 35 = 45.
dp of 0111 ending at C is 45.
Set 1001 = {A, D}, ending at D. The path arrived from the set without D, 0001 = {A}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is A: 0 + 20 = 20.
dp of 1001 ending at D is 20.
Set 1011 = {A, B, D}, ending at B. The path arrived from the set without B, 1001 = {A, D}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is D: 20 + 25 = 45.
dp of 1011 ending at B is 45.
Set 1011 = {A, B, D}, ending at D. The path arrived from the set without D, 0011 = {A, B}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is B: 10 + 25 = 35.
dp of 1011 ending at D is 35.
Set 1101 = {A, C, D}, ending at C. The path arrived from the set without C, 1001 = {A, D}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is D: 20 + 30 = 50.
dp of 1101 ending at C is 50.
Set 1101 = {A, C, D}, ending at D. The path arrived from the set without D, 0101 = {A, C}, which is one bit off and therefore a smaller number, so its row is already filled. Its only usable end is C: 15 + 30 = 45.
dp of 1101 ending at D is 45.
Set 1111 = {A, B, C, D}, ending at B. The path arrived from the set without B, 1101 = {A, C, D}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via C: 50 + 35 = 85, via D: 45 + 25 = 70. The cheapest is via D, 70.
dp of 1111 ending at B is 70.
Set 1111 = {A, B, C, D}, ending at C. The path arrived from the set without C, 1011 = {A, B, D}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via B: 45 + 35 = 80, via D: 35 + 30 = 65. The cheapest is via D, 65.
dp of 1111 ending at C is 65.
Set 1111 = {A, B, C, D}, ending at D. The path arrived from the set without D, 0111 = {A, B, C}, which is one bit off and therefore a smaller number, so its row is already filled. Try every end of that row: via B: 50 + 25 = 75, via C: 45 + 30 = 75. The cheapest is via B, 75.
dp of 1111 ending at D is 75.
The last row, 1111, holds every city. Each entry still has to return to A: end at B: 70 + 10 = 80, end at C: 65 + 15 = 80, end at D: 75 + 20 = 95. The cheapest tour costs 80.
The cheapest tour costs 80.
Cheapest tour: 80. The table has 8 x 4 cells, 13 of them reachable, filled with 15 additions in total, against 6 orderings by brute force. That gap is small for 4 cities and enormous for 20, where 2^20 x 20 states is about twenty million and 19! is beyond counting. Bitmask DP is the answer whenever the state is a subset of a small set: the subset becomes an integer, one bit per element, and increasing numeric order is a valid order of computation because a subset is always a smaller number than a set containing it.
Cheapest tour 80 with 13 states filled.