classSolution { int n, m; int dp[1<<17]; inthelper(int st){ if(!st) return0; if(dp[st]!= -1) return dp[st]; dp[st] = INT_MAX; for(int i = 0; i < n; i++) { for(int j =0; j < m; j++) { if(st & (1<<(i*m + j))) { int nt = st; for(int k = 0; k < n; k++) nt &= ~(1<<(k*m + j)); for(int k = 0; k < m; k++) nt &= ~(1<<(i*m + k)); dp[st] = min(dp[st], 1 + helper(nt)); } } } return dp[st]; } public: intremoveOnes(vector<vector<int>>& grid){ n = grid.size(), m = grid[0].size(); memset(dp,-1,sizeof(dp)); int state = 0; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(grid[i][j]) state |= 1<<(i*m+j); returnhelper(state); } };