上一題：LeetCode第62題: 不同路徑uniquePaths(C語(yǔ)言)
思路：參考62題的思路咏花，遞歸肯定要直接放棄啦矗蕊，同樣還是要考慮用動(dòng)態(tài)規(guī)劃來(lái)做拿愧。與62題不同的是杠河，初始化和計(jì)算的時(shí)候需要考慮障礙。
1赶掖、對(duì)于第1行和第1列感猛，一旦遇到障礙，則障礙后續(xù)的行列只能是0奢赂，因?yàn)楹罄m(xù)的方格無(wú)法抵達(dá)陪白；
2、對(duì)于其他行列的計(jì)算膳灶，如果該方格本身就是障礙咱士，則可以直接給該方格賦值0繼續(xù)；對(duì)于非障礙的方格轧钓，則要考慮該方格的左鄰居和上鄰居是否為障礙序厉，是障礙的話不計(jì)入結(jié)果內(nèi)即可。
注釋：代碼中的前兩個(gè)循環(huán)用于初始化首行和首列的
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
unsigned int a[obstacleGridSize][*obstacleGridColSize];
/*初始化第一列*/
for(int i = 0; i < obstacleGridSize; i++){
if(obstacleGrid[i][0] == 0)
a[i][0] = 1;
else{
for(int j = i; j < obstacleGridSize; j++)
a[j][0] = 0;
break;
}
}
/*初始化第一行*/
for(int i = 0; i < *obstacleGridColSize; i++){
if(obstacleGrid[0][i] == 0)
a[0][i] = 1;
else{
for(int j = i; j < *obstacleGridColSize; j++)
a[0][j] = 0;
break;
}
}
/*動(dòng)態(tài)規(guī)劃開(kāi)始計(jì)算*/
for(int i = 1; i < obstacleGridSize; i++){
for(int j = 1; j < *obstacleGridColSize; j++){
a[i][j] = 0;
if(obstacleGrid[i][j] == 1)
continue;
if(obstacleGrid[i-1][j] == 0)
a[i][j] += a[i-1][j];
if(obstacleGrid[i][j-1] == 0)
a[i][j] += a[i][j-1];
}
}
return a[obstacleGridSize - 1][*obstacleGridColSize - 1];
}
本系列文章毕箍，旨在打造LeetCode題目解題方法弛房，幫助和引導(dǎo)同學(xué)們開(kāi)闊學(xué)習(xí)算法思路，由于個(gè)人能力和精力的局限性而柑，也會(huì)參考其他網(wǎng)站的代碼和思路文捶，如有侵權(quán)，請(qǐng)聯(lián)系本人刪除媒咳。
