题目
题解： 动态规划，用二进制压缩状态，注意分析几种情况，就能推出来正确的状态转移方程。
代码语言：javascript复制class Solution {
public:
int dp[12][4096];
int connectTwoGroups(vector<vector<int>>& cost) {
int n = cost.size();
if (n == 0)
return 0;
int m = cost[0].size();
for (int i = 0; i < n; i )
{
for (int j = 0; j < (1 << m); j )
{
dp[i][j] = INT32_MAX;
for (int k = 0; k < m; k )
{
if (j & (1 << k))
{
if (i != 0 && dp[i - 1][j ^ (1 << k)] != INT32_MAX )
{
dp[i][j] = min(dp[i][j], dp[i - 1][j ^ (1 << k)] cost[i][k]);
}
if (i != 0 && (dp[i - 1][j] != INT32_MAX))
{
dp[i][j] = min(dp[i][j], dp[i-1][j] cost[i][k]);
}
if (i == 0 && (j ^ (1 << k)) == 0)
{
dp[i][j] = cost[i][k];
}
else
{
if (dp[i][j ^ (1 << k)] != INT32_MAX)
{
dp[i][j] = min(dp[i][j], dp[i][j ^ (1 << k)] cost[i][k]);
}
}
}
}
}
}
return dp[n - 1][(1 << m) - 1];
}
};
