现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。
测试样例：
[[0,1,0],[2,0,0]],2,3返回：2
思路：典型的动态规划题，以1在左上角，2在右上角为例。1只能向下或者向右走。先初始化1所在的列，遇见-1之前全部赋值为1，遇见0之后全赋值为0，同理再初始化行。边界以2为准。再根据 dp[row][col]=dp[row-1][col]+dp[row][col-1] 进行赋值，直到到达商店，直接返回该处的值即可。
解题思路：
1.首先找到1和2的位置，这里要注意一点，从1走到2与从2走到1所得的路径数相同，即以1为起点或以2为起点是等价的。所以我做的处理是，统一从行坐标小的位置走到行坐标大的位置，即向下走。
2.1和2的相对位置可以归纳如下：
（1）两者位于主对角线上
（2）两者位于副对角线上
（3）两者位置重合或处于同一行或同一列（该特殊情形可以合并到（1）（2）中）
3.接下来的问题就是分别对向左走和向右走的情形应用动态规划求解。
代码如下：
public int countPath(int[][] map, int n, int m) { int startX = 0, startY = 0, endX = 0, endY = 0; for (int i = 0; i < n; i++) { for (int j = 0; j endX) { int tmpx = startX; startX = endX; endX = tmpx; int tmpy = startY; startY = endY; endY = tmpy; } int pt[][] = new int[n][m]; if (startY < endY) { pt[startX][startY] = 1; //初始化列 for (int i = startX + 1; i <= endX; i++) { pt[i][startY] = (pt[i][startY] == -1) ? 0 : pt[i - 1][startY]; } //初始化行 for (int i = startY+1; i <=endY; i++) { pt[startX][i] = (pt[startX][i] == -1) ? 0 : pt[startX][i-1]; } for (int i = startX+1; i <=endX; i++) { for (int j =startY+1; j <=endY; j++) { pt[i][j]=map[i][j]==-1?0:pt[i-1][j]+pt[i][j-1]; } } } else { pt[startX][startY] = 1; //初始化列 for (int i = startX + 1; i <= endX; i++) { pt[i][startY] = (pt[i][startY] == -1) ? 0 : pt[i - 1][startY]; } //初始化行 for (int i = startY-1; i>=endY; i--) { pt[startX][i] = (pt[startX][i] == -1) ? 0 : pt[startX][i+1]; } for (int i = startX+1; i <=endX; i++) { for (int j =startY-1; j>=endY; j--) { pt[i][j]=map[i][j]==-1?0:pt[i-1][j]+pt[i][j+1]; } } } return pt[endX][endY]; }