LintCode练习——炸弹袭击（动态规划）

题目描述：

你只能在空的地方放置炸弹.

思路：

这里炸弹是可以把所在行和所在列的所有敌人都炸死，言外之意就是可以向四个方向炸，如果我们只要能求出一个方向，那么另外三个方向同理也能求出来。为了方便，这里我们假设所有点都可以放炸弹（后面再做相关处理），现在的问题就是如何求一个点它向上炸的敌人的数量。我们开辟两个二维数组，一个A[][], 一个dp[][]，dp数组用来存放每个方向的，算出一个方向，就累加到A数组上，等所有方向都枚举完，最后我们再找出所有为空地'0'的点的四个方向炸敌人之和最大的这个数即可。

利用动态规划算法求解：

1、定义状态：dp[i][j] 表示点(i, j)向某个方向能炸的敌人数，A[i][j] 表示点(i, j)往四个方向上炸死的敌人的总数

2、转移方程（这里我们只枚举向上的情况）：

　　① 如果（i，j）为空地‘0’ ，那么dp[i][j] = dp[i - 1][j];

　　② 如果（i，j）为墙‘W’ ，那么dp[i][j] = 0;

　　③ 如果（i，j）为敌人‘E’ ，那么dp[i][j] = dp[i - 1][j] + 1;

3、初始条件和边界范围：这里不需要处理

4、最后返回A[i][j]<1<=i<=M, 1<=j<=N>中最大的那个数，即该点炸敌人数最多

AC代码：

  1 public class Solution {
  2     /**
  3      * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0'
  4      * @return: an integer, the maximum enemies you can kill using one bomb
  5      */
  6     public int maxKilledEnemies(char[][] grid) {
  7         // write your code here
  8         if (grid == null || grid.length == 0 || grid[0].length == 0) {
  9             return 0;
 10         }
 11 
 12         int m = grid.length;
 13         int n = grid[0].length;
 14 
 15         // 坐标型动态规划
 16         int[][] dp = new int[m][n];
 17         int[][] A = new int[m][n];
 18         
 19         // 依次考虑上下左右四个方向
 20         // up
 21         for (int i = 0; i < m; i++) {
 22             for (int j = 0; j < n; j++) {
 23                 // 初始化为0
 24                 dp[i][j] = 0;
 25                 if (grid[i][j] == 'W') {
 26                     // 如果是墙 ,一票否决
 27                     continue;
 28                 }
 29 
 30                 if (grid[i][j] == 'E') {
 31                     dp[i][j] = 1;
 32                 }
 33 
 34                 if (i - 1 >= 0) {
 35                     dp[i][j] += dp[i - 1][j];
 36                 }
 37 
 38                 // 先做累加
 39                 A[i][j] += dp[i][j];
 40             }
 41         }
 42 
 43         // down
 44         for (int i = m - 1; i >= 0; i--) {
 45             for (int j = 0; j < n; j++) {
 46                 // 初始化为0
 47                 dp[i][j] = 0;
 48                 if (grid[i][j] == 'W') {
 49                     // 如果是墙 ,一票否决
 50                     continue;
 51                 }
 52 
 53                 if (grid[i][j] == 'E') {
 54                     dp[i][j] = 1;
 55                 }
 56 
 57                 if (i + 1 < m) {
 58                     dp[i][j] += dp[i + 1][j];
 59                 }
 60 
 61                 // 先做累加
 62                 A[i][j] += dp[i][j];
 63             }
 64         }
 65 
 66         // left
 67         for (int i = 0; i < m; i++) {
 68             for (int j = 0; j < n; j++) {
 69                 // 初始化为0，防止后面每次都要重置为0
 70                 dp[i][j] = 0;
 71                 if (grid[i][j] == 'W') {
 72                     // 如果是墙 ,一票否决
 73                     continue;
 74                 }
 75 
 76                 if (grid[i][j] == 'E') {
 77                     dp[i][j] = 1;
 78                 }
 79 
 80                 if (j - 1 >= 0) {
 81                     dp[i][j] += dp[i][j - 1];
 82                 }
 83 
 84                 // 先做累加
 85                 A[i][j] += dp[i][j];
 86             }
 87         }
 88 
 89         // right
 90         for (int i = 0; i < m; i++) {
 91             for (int j = n - 1; j >= 0; j--) {
 92                 // 初始化为0
 93                 dp[i][j] = 0;
 94                 if (grid[i][j] == 'W') {
 95                     // 如果是墙 ,一票否决
 96                     continue;
 97                 }
 98 
 99                 if (grid[i][j] == 'E') {
100                     dp[i][j] = 1;
101                 }
102 
103                 if (j + 1 < n) {
104                     dp[i][j] += dp[i][j + 1];
105                 }
106 
107                 // 先做累加
108                 A[i][j] += dp[i][j];
109             }
110         }
111 
112         int ans = 0;
113         // 计算
114         for (int i = 0; i < m; i++) {
115             for (int j = 0; j < n; j++) {
116                 if (grid[i][j] == '0') {
117                     if (A[i][j] > ans) {
118                         ans = A[i][j];
119                     }
120                 }
121             }
122         }
123 
124         // 返回结果
125         return ans;
126     }
127 }

LintCode练习——炸弹袭击（动态规划）

题目描述：

样例

注意事项

思路：

利用动态规划算法求解：

AC代码：

推荐阅读