一. 62——不同路徑
題目
思路：
以4*4的矩陣為例（如下圖），首先考慮行數(shù)為1的情況（最下面一行）强重，每個格子除了往右走之外別無選擇亲怠，因此從這個格子出發(fā)可能的路徑都是1，然后在此基礎(chǔ)上考慮倒數(shù)第二行（從最右邊的列開始）运吓，最后一列只能往下渴邦，有一種選擇，倒數(shù)第二列可以往右或者往下拘哨，因此它的可能的選擇等于它右邊一格的選擇數(shù)加上下邊一格的選擇數(shù)（1+1=2）谋梭，同樣的，第二列的選擇數(shù)等于右邊的2+下邊的1=3倦青，因此瓮床，我們可以得出結(jié)論，就是每一格的選擇數(shù)等于它右邊的格加下邊的格的選擇數(shù)产镐。
4*4的格子的可選路徑數(shù)
實現(xiàn)方法隘庄，初始化一個一維數(shù)組，長度為格子的列數(shù)癣亚，然后先得到倒數(shù)第一行丑掺，再得到倒數(shù)第二行，以此類推述雾，最后數(shù)組的第一個元素就是結(jié)果：
代碼：
public static int uniquePaths(int m, int n) {
int[] arr=new int[m];
Arrays.fill(arr, 1);
for(int row=1;row<n;row++){
for(int col=m-2;col>=0;col--){
arr[col]=arr[col]+arr[col+1];
}
}
return arr[0];
}
一. 63——不同路徑2
題目
思路：
和上一道題類似街州，區(qū)別在于如果矩陣中這個格子有障礙，則把他置0即可绰咽，下圖是一個有障礙的4*4的格子和它對應(yīng)的路徑數(shù)表格菇肃，需要注意的一點是如果最后一行的某一個有障礙，那么這一行左邊的路徑數(shù)都是0取募，如果最右邊的一列的某一格有障礙琐谤，那么這一列上面的所有路徑數(shù)都是0
4*4的有障礙矩陣
代碼：
public static int uniquePathsWithObstacles(int[][] arr) {
int rowNum=arr[0].length;
int[] pArr=new int[arr.length];
for(int i=arr.length-1;i>=0;i--){
if(arr[i][rowNum-1]==0){
pArr[i]=1;
}else{
while(i>=0)pArr[i--]=0;
}
}
for(int row=rowNum-2;row>=0;row--){
for(int col=arr.length-1;col>=0;col--){
if(arr[col][row]==1)pArr[col]=0;
else{
if(col!=arr.length-1) pArr[col]=pArr[col]+pArr[col+1];
}
}
}
return pArr[0];
}
