Bomb Enemy

此题的状态方程很容易看出来，但主要问题在于第一时间拿到这道题的时候可能会误判此题是BFS类型的题目

dp[i][j] = dp[i - 1][j] + dp[i + 1][j] + dp[i][j - 1] + dp[i][j + 1]

上面这个这个状态方程已经表明了这不是一个单纯的矩阵递推动态规划而是需要首先从左上角dp[i][j - 1]和dp[i - 1][j]两个状态，再从右下角推dp[i + 1][j]和dp[i][j + 1]两个状态，最后将两个递推的和加起来判最大杀伤数，所以这里的矩阵初始化也是很少见的要在输入矩阵的四边全部加入围栏以简化逻辑 另外此题是可以进行空间优化到O(n)，虽然我不知道怎么优化_(:зゝ∠)_

class Solution(object):
    def maxKilledEnemies(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        n = len(grid)
        if not n:
            return 0

        m = len(grid[0])
        if not m:
            return 0

        ref = [([[0, 0]] * (m + 2)) for _ in xrange(n + 2)]
        for i in xrange(1, n + 1):
            for j in xrange(1, m + 1):
                if grid[i - 1][j - 1] == 'W':
                    ref[i][j] = [0, 0]
                elif grid[i - 1][j - 1] == 'E':
                    ref[i][j] = [ref[i][j - 1][0] + 1, ref[i - 1][j][1] + 1]
                else:
                    ref[i][j] = [ref[i][j - 1][0], ref[i - 1][j][1]]

        for i in xrange(n, 0, -1):
            for j in xrange(m, 0, -1):
                if grid[i - 1][j - 1] == 'W':
                    ref[i][j] = [0, 0]
                else:
                    ref[i][j] = [max(ref[i][j + 1][0], ref[i][j][0]), max(ref[i + 1][j][1], ref[i][j][1])]

        result = 0
        for i in xrange(n):
            for j in xrange(m):
                if grid[i][j] == '0':
                    result = max(result, sum(ref[i + 1][j + 1]))

        return result