【问题】有一个机器人的位于一个 m × n个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？

【分析】最后一步：要么从左边来，要么从上边来，故dp[i][j] = dp[i][j-1] + dp[i-1][j]

public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//初始化dp[0][0] = 1;//初始化第一行for (int j = 0; j < n; j++) {dp[0][j] = 1;}//初始化第一列for (int i = 0; i < m; i++) {dp[i][0] = 1;}//处理其他for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}

【问题】上一题的跟进问题，现在考虑网格中有障碍物，那样将会有多少条不同的路径？网格中的障碍和空位置分别用 1 和 0 来表示。

【分析】从最后一步出发，要选一条没有障碍的路径到达右下角，当前位置i,j所有可能路径依然是 dp[i] [j] = dp[i] [j-1] + dp[i-1] [j]，但必须是没有障碍的

• 起点和终点若有障碍，直接返回0
• 初始化第一行和第一列，也要考虑有障碍的情况
• 起点和终点没有障碍，若途中碰到障碍了，令dp[i][j] = 0，表示不可达

public int uniquePathsWithObstacles(int[][] A) {int n = A.length;int m = A[0].length;//判断起点和终点有没有障碍，有障碍直接返回0if (A[0][0] == 1 || A[n - 1][m - 1] == 1) {return 0;}int[][] dp = new int[n][m];//初始化dp[0][0] = 1;int i, j;//初始化第一行for (j = 1; j < m; j++) {if (A[0][j] == 1) {dp[0][j] = 0;} else {dp[0][j] = dp[0][j - 1];}}//初始化第一列for (i = 1; i < n; i++) {if (A[i][0] == 1) {dp[i][0] = 0;} else {dp[i][0] = dp[i - 1][0];}}//处理其他for (i = 1; i < n; i++) {for (j = 1; j < m; j++) {if (A[i][j] == 1) {dp[i][j] = 0;continue;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];} }}return dp[n - 1][m - 1];}

【问题】给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）

【分析】也就是求“最长连续单调子序列”，也就是LIS+LDS。实际上只要求个LIS再倒过来求一遍。

public int longestIncreasingContinuousSubsequence(int[] A) {int res = LIS(A);//倒过来求一遍int i = 0;int j = A.length - 1;while (i < j) {int temp = A[i];A[i] = A[j];A[j] = temp;i++;j--;}return Math.max(res, LIS(A));}public int LIS(int[] A) {int n = A.length;if (n == 0) {return 0;}int[] dp = new int[n];int res = 1;        //最少长度是1dp[0] = 1;  for (int i = 1; i < n; i++) {//长度至少是1，它本身dp[i] = 1;if (A[i] > A[i - 1]) {dp[i] = dp[i - 1] + 1;}res = Math.max(res, dp[i]);}return res;}

【问题】给定一个只含非负整数的m x n网格，找到一条从左上角到右下角的可以使数字和最小的路径。简而言之求最小路径和。

//普通方式
public int minPathSum(int[][] A) {int n = A.length;int m = A[0].length;int[][] dp = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 && j == 0) {dp[i][j] = A[0][0];continue;}dp[i][j] = Integer.MAX_VALUE;//来自上方的情况if (i > 0) {dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + A[i][j]);}//来自左侧的情况if (j > 0) {dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + A[i][j]);}}}return dp[n-1][m - 1];}

使用滚动数组进行优化，当前行只和上面一行有关系，实际上只需要开两行，使用old和new指针，old存放i-1行，new存放当前第i行，关键语句在于old和now进行交换

old = now;

now = 1 - now

//滚动数组优化
//只需要把i变为now，i-1变为old即可
public int minPathSum(int[][] A) {int n = A.length;int m = A[0].length;int[][] dp = new int[2][m];int old = 0, now = 0;for (int i = 0; i < n; i++) {old = now;now = 1 - now;for (int j = 0; j < m; j++) {if (i == 0 && j == 0) {dp[now][j] = A[0][0];continue;}dp[now][j] = Integer.MAX_VALUE;//来自上方if (i > 0) {dp[now][j] = Math.min(dp[now][j], dp[old][j] + A[i][j]);}//来自左侧if (j > 0) {dp[now][j] = Math.min(dp[now][j], dp[now][j - 1] + A[i][j]);}}}return dp[now][m - 1];}

【问题】给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 ‘0’), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁。

【分析】原本只能在空地放炸弹，现在假设有敌人和有墙的地方也能放炸弹，有敌人的地方，格子里的敌人能被炸死，再加上其他炸死的人，有墙的地方，炸死人数为0。现在分析一个方向，比如向上，有三种情况：

• （i,j）是空地：结果就是从（i-1,j）格开始向上能炸死的敌人数
• （i,j）是敌人：结果就是从（i-1,j）格开始向上能炸死的敌人数 + 1
• （i,j）是墙：0

原来要求（i,j）格子放炸弹向上能炸死的敌人数，子问题就转化为（i-1,j）格向上能炸死的敌人数，上述三种情况就如下：

• Up[i][j] = Up[i-1][j]，(i,j)是空地的情况
• Up[i][j] = Up[i-1][j] + 1，(i,j)是敌人的情况
• Up[i][j] = 0，(i,j)是墙的情况

初始条件就是第0行，如果是敌人，向上炸死人数为1，如果是空地或墙，向上炸死人数为0。

另外三个方向Down[i][j], Left[i][j], Right[i][j]也是一样考虑。炸死的敌人数就是四个方向加起来，每次更新一下最大值。

public static int maxKilledEnemies(char[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int[][] up = new int[m][n];int[][] down = new int[m][n];int[][] left = new int[m][n];int[][] right = new int[m][n];int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//i,j处为炸弹放置的位置//如果是墙,其实四种情况都是0if (grid[i][j] == 'W') {up[i][j] = 0;continue;}up[i][j] = grid[i][j] == 'E' ? 1 : 0;if (i > 0) {up[i][j] += up[i - 1][j];}}}//down应该从下往上算，自底向上for (int i = m - 1; i >= 0; i--) {for (int j = 0; j < n; j++) {if (grid[i][j] == 'W') {down[i][j] = 0;continue;}down[i][j] = grid[i][j] == 'E' ? 1 : 0;if (i < m - 1) {down[i][j] += down[i + 1][j];}}}//left，从左往右算for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 'W') {left[i][j] = 0;continue;}left[i][j] = grid[i][j] == 'E' ? 1 : 0;if (j > 0) {left[i][j] += left[i][j - 1];}}}//right，从右往左算for (int i = 0; i < m; i++) {for (int j = n - 1; j >= 0; j--) {if (grid[i][j] == 'W') {right[i][j] = 0;continue;}right[i][j] = grid[i][j] == 'E' ? 1 : 0;if (j < n - 1) {right[i][j] += right[i][j + 1];}}}//结果填充dpint res = Integer.MIN_VALUE;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//只有在空地能放炸弹if (grid[i][j] == '0') {dp[i][j] = up[i][j] + down[i][j] + left[i][j] + right[i][j];if (dp[i][j] > res) {res = dp[i][j];}}}}if (res != Integer.MIN_VALUE) {return res;} else {return 0;}}