题目描述

https://www.nowcoder.com/practice/3d1adf0f16474c90b27a9954b71d125d

题解

动态规划

假如有四个城市 0, 1, 2, 3，选定城市 0 为起点，那么其他三个城市用一个 3位的二进制数表示，即为 111，表示这三个城市都没去过。3位二进制数一共有 $2^3 = 8$ 种状态。

最终花销可表示为 dp[0][111]，假设我们先从城市 0 到城市 1，那么 dp[0][111] = cost[0][1] + dp[1][011]，即为从城市 0 到城市 1 的花销加上从城市 1 到其他所有还没去过的城市的总花销。

注意最终要返回起点城市 0，所以 dp[i][0] = cost[i][0]，i = 0, …, n - 1。于是二维数组 int dp[n][pow(2, n - 1)] 即记录了所有的可能性。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int> > cost(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
    // n 个城市，除掉起点城市 0，还有 n - 1 个城市，一共有 all = pow(2, n - 1) 个状态
    int all = 1 << (n - 1);     // 对应位数为 1 代表该城市还没去，为 0 代表去过了
    vector<vector<int> > dp(n, vector<int>(all, 0));
    // 按列填入，第一列、第二列...，保证下面动态转移方程是有效值计算
    for (int j = 0; j < all; j++) {
        for (int i = 0; i < n; i++) {
            if (j == 0) {   // 第一列，n-1位全零，dp[i][0] 即为回到起点城市的花费 cost[i][0]
                dp[i][j] = cost[i][j];
            } else {
                dp[i][j] = INT_MAX;
                for (int k = 1; k < n; k++) {   // 遍历 n-1 个城市
                    // index = 0001, 0010, 0100, 1000, ...
                    int index = 1 << (k - 1);   // index 代表一个去过或没去过的非起点城市k
                    if (index & j) {    // 如果城市 k 还没去过
                        // 设定 k 为下一个要去的城市
                        int others = index ^ j;     // 将第 k 位置为 0
                        // 比如 4 个城市，从城市 0 出发，其他城市状态为 111
                        // 如果下一个要去城市 1，那么 dp[0][111] = cost[0][1] + dp[1][011]
                        // dp 即为总花费，这里计算 [111] 时，[011] 一定是有效值
                        // 因为是按列从左往右填入，而 1 的数量较多的状态 [111] 一定在 [011] 的右
                        dp[i][j] = min(dp[i][j], cost[i][k] + dp[k][others]);
                    }
                }
                // 将所有没去过的城市都假设一遍，最终取最小值，填入了 dp[i][j]
            }
        }
        // 到此填完一列，继续下一列
    }
    // 最后总花费即为从起点城市 0 出发，到全 1 的状态
    cout << dp[0][all - 1] << endl;
    return 0;
}