class Solution
{
public:
	int cost;
	std::vector<int> citiesInOrder;
};

class SearchWrapper
{
public:
	int startCity;
	int mask;
};

std::vector<std::vector<int>> matrix;
std::map<SearchWrapper, Solution> solutionsMap;

Solution DynamicProgrammingSolver::solveRecursive(int mask, int startCity) {
	Solution solution1;
	if (mask == (1 << matrix.size()) - 1) {
		solution1.citiesInOrder.push_back(startCity);
		solution1.cost = matrix[startCity][0];
		return solution1;
	}
	Solution solution2;
	solution2.cost = INT_MAX;

	for (int city = 0; city < matrix.size(); city++) {
		if ((mask & (1 << city)) == 0) {
			SearchWrapper searchWrapper;
			searchWrapper.startCity = city;
			searchWrapper.mask = mask | (1 << city);
			Solution solutionFromMap = solutionsMap[searchWrapper];
			Solution someSolution;
			if (solutionFromMap.cost == 0) {
				someSolution = solveRecursive(mask | (1 << city), city);
			}
			else {
				someSolution = solutionFromMap;
			}
			Solution finalSolution;
			finalSolution.cost = matrix[startCity][city] + someSolution.cost;
			finalSolution.citiesInOrder.push_back(startCity);
			finalSolution.citiesInOrder.insert(finalSolution.citiesInOrder.end(),
				someSolution.citiesInOrder.begin(), someSolution.citiesInOrder.end());
			if (solution2.cost > finalSolution.cost) {
				solution2 = finalSolution;
			}
			SearchWrapper searchWrapperToInsert;
			searchWrapperToInsert.startCity = city;
			searchWrapperToInsert.mask = mask | (1 << city);
			solutionsMap[searchWrapperToInsert] = finalSolution;
			int x = 5;
		}
	}
	return solution2;
}

wywołanie tej funkcji: solveRecursive(1,0);