I want the solution in Python please. It's a Travelling salesman problem with Dynamic Programming.

Thank you

Always Catch your Mon, Inc., (also know as ACM), wants to create a new product, called Pokmon Go Go. Users can purchase this application to help them play Pokmon go. The software accesses the pokstop locations near the current location as well as a list of Pokmon that can be found at each stop. The application then computes the shortest route one can follow to catch all the unique Pokmon, and return to the starting point. The program assumes that the user is in a city where travel is restricted to moving only in the north-south and east-west directions. The program also assumes that all pok stops are on the intersection of two roads. For example, consider a case where the application finds five nearby pok stops. Each stop's location is indicated by two integers, (r.c), where r is the number of blocks north of your starting position and c is the number of blocks west of your starting position. Consider if the locations of the five pok stops are (5,9), (20, 20), (1, 1), (1,8) and (2,8) while the names of the Pokmon found at these stops are Evevee, Flareon, Flareon, Jolteon, and Umbreon, respectively. It is clear that one does not have to visit both the second and third stops, since the same Pokmon can be caught at either of them. The best route is to visit the first, fifth, fourth, and third stops (in that order) for a total distance of 28 blocks, since: The distance from (0,0) to (5,9) is 14. The distance from (5,9) to (2,8) is 4. The distance from (2,8) to (1,8) is 1. The distance from (1,8) to (1,1) is 7. The distance from (1,1) to (0,0) is 2. Input The input holds a single test case. The test case begins with a single integer n, 0<>