使用动态规划法解决tsp问题，c++编程

动态规划是求解旅行商问题（Traveling Salesman Problem, TSP）的一种常用算法。TSP是一个经典的组合优化问题，目标是最短路径，即找到访问所有城市一次并返回起点的最短路径。

在C++中，动态规划可以采用“记忆化搜索”（也叫自底向上）的方式。关键步骤包括：

1. 定义状态：通常表示为一个数组或二维数组，每个元素`dp[i]`代表从起始城市出发到第i个城市，并返回到起始城市的最小成本。

2. 状态转移方程：对于任意两个相邻的城市i和j，从起始城市出发经过i再经j的成本等于当前已经访问过的(i-1)个城市加上直接从i到j的成本，然后选择这个总成本与直接跳过i经j的成本中的较小者作为新的状态值。

int dp[cityNum][cityNum];
dp[0][i] = dist[0][i]; // 初始状态，起点到各个点的距离
for (int i = 1; i < cityNum; ++i) {
    for (int j = 0; j < i; ++j) {
        dp[i][j] = min(dp[i - 1][j] + dist[j][i], dp[i][i - 1]); // 动态规划更新
    }
}

3. 最终解决方案：`dp[cityNum - 1][0]`就是整个路径的最小成本。为了找出具体的路线，可以使用回溯法，从最后一个城市开始，逐步构建路径。

vector<int> path;
path.push_back(cityNum - 1);
while (true) {
    int lastCity = path.back();
    for (int nextCity : cities) { // 遍历未访问的城市
        if (lastCity != nextCity && dp[lastCity][nextCity] == dp[cityNum - 1][lastCity]) {
            path.push_back(nextCity);
            break;
        }
    }
    if (lastCity == 0) break;
    reverse(path.begin(), path.end());
}