1. class Solution
2. {
3. public:
4.         int cost;
5.         std::vector<int> citiesInOrder;
6. };
7.  
8. class SearchWrapper
9. {
10. public:
11.         int startCity;
12.         int mask;
13. };
14.  
15. std::vector<std::vector<int>> matrix;
16. std::map<SearchWrapper, Solution> solutionsMap;
17.  
18. Solution DynamicProgrammingSolver::solveRecursive(int mask, int startCity) {
19.         Solution solution1;
20.         if (mask == (1 << matrix.size()) - 1) {
21.                 solution1.citiesInOrder.push_back(startCity);
22.                 solution1.cost = matrix[startCity][0];
23.                 return solution1;
24.         }
25.         Solution solution2;
26.         solution2.cost = INT_MAX;
27.  
28.         for (int city = 0; city < matrix.size(); city++) {
29.                 if ((mask & (1 << city)) == 0) {
30.                         SearchWrapper searchWrapper;
31.                         searchWrapper.startCity = city;
32.                         searchWrapper.mask = mask | (1 << city);
33.                         Solution solutionFromMap = solutionsMap[searchWrapper];
34.                         Solution someSolution;
35.                         if (solutionFromMap.cost == 0) {
36.                                 someSolution = solveRecursive(mask | (1 << city), city);
37.                         }
38.                         else {
39.                                 someSolution = solutionFromMap;
40.                         }
41.                         Solution finalSolution;
42.                         finalSolution.cost = matrix[startCity][city] + someSolution.cost;
43.                         finalSolution.citiesInOrder.push_back(startCity);
44.                         finalSolution.citiesInOrder.insert(finalSolution.citiesInOrder.end(),
45.                                 someSolution.citiesInOrder.begin(), someSolution.citiesInOrder.end());
46.                         if (solution2.cost > finalSolution.cost) {
47.                                 solution2 = finalSolution;
48.                         }
49.                         SearchWrapper searchWrapperToInsert;
50.                         searchWrapperToInsert.startCity = city;
51.                         searchWrapperToInsert.mask = mask | (1 << city);
52.                         solutionsMap[searchWrapperToInsert] = finalSolution;
53.                         int x = 5;
54.                 }
55.         }
56.         return solution2;
57. }
58.  
59. wywołanie tej funkcji: solveRecursive(1,0);
60.  
61.  
62.