# Clean C++ O(MN) time & space solution with detailed comments

• Whether you want to call this "DP solution", I think it is really based on personal philosophy how you want to interpret DP technique.

``````    int maxKilledEnemies(vector<vector<char>>& g) {
int m, n, res = 0;
if (!(m = g.size())||!(n = g[0].size())) return res;

// enemies killed vertically/horizontally at (i,j)
vector<vector<int>> v(m, vector<int>(n)), h(m, vector<int>(n));

// calculate top and left including current location
// this is also the vertical kills total if location at bottom
// this is also the horizontal kills total if location at rightmost
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (g[i][j] != 'W') {
h[i][j] = (i? h[i-1][j] : 0) + (g[i][j] == 'E');
v[i][j] = (j? v[i][j-1] : 0) + (g[i][j] == 'E');
}

// calculate h[][] and v[][] and max total
for (int i = m-1; i >= 0; --i)
for (int j = n-1; j >= 0; --j)
if (g[i][j] != 'W') {
// total horizontal kills must be same if neither (i,j) or (i+1,j) is wall
if (i+1 < m && h[i+1][j]) h[i][j] = h[i+1][j];
// total vertical kills must be same if neither (i,j) or (i,j+1) is wall
if (j+1 < n && v[i][j+1]) v[i][j] = v[i][j+1];
if (g[i][j] == '0') res = max(res, h[i][j] + v[i][j]);
}

return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.