leetcode1595 连通两组点的最小成本

思路：

状压dp。

实现：

 1 class Solution {
 2 public:
 3     int connectTwoGroups(vectorint>>& cost) {
 4         int n=cost.size(),m=cost[0].size();
 5         vectorint>>mp(n,vector<int>(1<0));
 6         for(int i=0;i){
 7             for(int j=0;j<1<){
 8                 int k=j;
 9                 int id=0;
10                 int sum=0;
11                 while(k){
12                     if(k&1){
13                         sum+=cost[i][id];
14                     }
15                     k>>=1;
16                     id++;
17                 }
18                 mp[i][j]=sum;
19             }
20         }
21         vectorint>>dp(n,vector<int>(1<0x3f3f3f3f));
22         for(int j=0;j<1<){
23             dp[0][j]=mp[0][j];
24         }
25         for(int i=1;i){
26             for(int j=0;j<1<){
27                 int k=j;
28                 int id=0;
29                 while(k){
30                     if(k&1){
31                         dp[i][j]=min(dp[i][j],dp[i-1][j]+cost[i][id]);
32                     }
33                     k>>=1;
34                     id++;
35                 }
36                 for(int k=j;k;k=(k-1)&j){
37                     if(k==j)continue;
38                     dp[i][j]=min(dp[i][j],dp[i-1][k]+mp[i][j-k]);
39                 }
40             }
41         }
42         return dp[n-1][(1<1];
43     }
44 };