### [553.炸弹袭击](https://www.lintcode.com/problem/bomb-enemy/) 给定一个二维矩阵, 每一个格子可能是一堵墙`W`,或者 一个敌人`E`或者空`0`(数字 '0'), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁. #### 1. 暴力解法 ```cpp class Solution { public: /** * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0' * @return: an integer, the maximum enemies you can kill using one bomb */ int maxKilledEnemies(vector<vector<char>> &grid) { // write your code here int m = grid.size(); if (m == 0) return 0; int n = grid[0].size(); int result = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 你只能在空的地方放置炸弹 if (grid[i][j] == '0') { int num = 0; // 同列向上 int k = i; while (k-1 >= 0 && grid[k-1][j] != 'W') { k--; if (grid[k][j] == 'E') { num++; } } // 同列向下 k = i; while (k+1 < m && grid[k+1][j] != 'W') { k++; if (grid[k][j] == 'E') { num++; } } //同行向左 k = j; while (k-1 >= 0 && grid[i][k-1] != 'W') { k--; if (grid[i][k] == 'E') { num++; } } //同行向右 k = j; while (k+1 < n && grid[i][k+1] != 'W') { k++; if (grid[i][k] == 'E') { num++; } } if (num > result) { result = num; } } } } return result; } }; ``` 结果：94%数据通过测试，时间复杂度过高 #### 2.动态规划解法 ```cpp class Solution { public: /** * @param grid: Given a 2D grid, each cell is either 'W', 'E' or '0' * @return: an integer, the maximum enemies you can kill using one bomb */ int maxKilledEnemies(vector<vector<char>> &grid) { // write your code here int m = grid.size(); if (m == 0) return 0; int n = grid[0].size(); // 向上能炸死多少人 vector<vector<int>> up(m, vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] != 'W') { if (grid[i][j] == 'E') { up[i][j] = 1; } if (i - 1 >= 0) { up[i][j] += up[i-1][j]; } } } } // 向下能炸死多少人 vector<vector<int>> down(m, vector<int>(n)); for (int i = m - 1; i >= 0; i--) { for (int j = 0; j < n; j++) { if (grid[i][j] != 'W') { if (grid[i][j] == 'E') { down[i][j] = 1; } if (i + 1 < m) { down[i][j] += down[i+1][j]; } } } } // 向左能炸死多少人 vector<vector<int>> left(m, vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] != 'W') { if (grid[i][j] == 'E') { left[i][j] = 1; } if (j - 1 >= 0) { left[i][j] += left[i][j-1]; } } } } // 向右能炸死多少人 vector<vector<int>> right(m, vector<int>(n)); for (int i = 0; i < m; i++) { for (int j = n - 1; j >= 0; j--) { if (grid[i][j] != 'W') { if (grid[i][j] == 'E') { right[i][j] = 1; } if (j + 1 < n) { right[i][j] += right[i][j+1]; } } } } int result = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '0') { int num = up[i][j] + down[i][j] + left[i][j] + right[i][j]; if (num > result) { result = num; } } } } return result; } }; ``` #### [322\. 零钱兑换](https://leetcode-cn.com/problems/coin-change/) ```cpp class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { int res = dp[i]; for (auto c : coins) { if (i >= c) { res = min(res, dp[i - c] + 1); } } dp[i] = res; } return dp[amount] == amount + 1 ? -1 : dp[amount]; } }; ```