5.5
还是用了一个新的数组来存储从 obstacleGrid[ i ] [ j ]到右下角的路径数目。
注释掉的部分，分别对最后一列和最后一行初始化，再处理中间部分，用三次for循环，果然超时了。
后来想到，可以把arrTmp数组的大小定义为【m+1】【n+1】，这样就可以省去初始化的部分。
只需将arrTmp【m】【n】初始化即可。
这里也出现了一个小问题，arrTmp【m】【n】的值不可以简单的设置为1，还需要考虑obstacleGrid【m】【n】的值。
大概就是这些问题吧。
public class Solution { /** * @param obstacleGrid: A list of lists of integers * @return: An integer */ public int uniquePathsWithObstacles(int[][] obstacleGrid) { // write your code here int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] arrTmp = new int[m+1][n+1]; arrInit(obstacleGrid,arrTmp,m,n); /* for(int i = 0;i <= m;i++){ for(int j = 0; j<=n;j++){ System.out.print(arrTmp[i][j] + " "); } System.out.println(""); } */ return arrTmp[0][0]; } public void arrInit(int[][] obstacleGrid,int[][] arrTmp,int m,int n){ /*for(int i = m-1;i >= 0;i--){ if(obstacleGrid[i][n-1] == 1){ for(int j = 0;j <=i;j++){ arrTmp[i][n-1] = 0; } break; } else{ arrTmp[i][n-1] = 1; } } System.out.println("初始化完成1"); for(int i = n-1;i >=0;i--){ if(obstacleGrid[m-1][i] ==1){ for(int j = 0;j<=j ;j++){ arrTmp[m-1][i] = 0; } break; } else{ arrTmp[m-1][i] = 1; } } System.out.println("初始化完成2"); for(int i = m-2;i>=0;i--){ for(int j = n-2;j>=0;j--){ if(obstacleGrid[i][j] == 1){ arrTmp[i][j] = 0; } else{ arrTmp[i][j] = arrTmp[i+1][j] + arrTmp[i][j+1]; } } } System.out.println("初始化完成3"); */ for(int i = m-1;i >= 0;i--){ for(int j = n-1;j >= 0;j--){ if(i == m-1 && j == n-1){ if(obstacleGrid[i][j] == 1){ arrTmp[i][j] = 0; } else{ arrTmp[i][j] = 1; } continue; } if(obstacleGrid[i][j] == 1){ arrTmp[i][j] = 0; } else{ arrTmp[i][j] = arrTmp[i+1][j] + arrTmp[i][j+1]; } } } } }