題目描述
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）歼跟。
機(jī)器人每次只能向下或者向右移動(dòng)一步望浩。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）琅锻。
問(wèn)總共有多少條不同的路徑齐婴？
說(shuō)明：m 和 n 的值均不超過(guò) 100诸老。
相關(guān)話題：?數(shù)組团南、動(dòng)態(tài)規(guī)劃???難度：?中等
示例 1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開(kāi)始群凶，總共有 3 條路徑可以到達(dá)右下角插爹。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3
輸出: 28
思路：
該題是典型的計(jì)數(shù)型動(dòng)態(tài)規(guī)劃，具體思路見(jiàn)動(dòng)態(tài)規(guī)劃请梢。
class Solution {
public int uniquePaths(int m, int n) {
int[][] paths = new int[m][n];
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
if(i == 0 || j == 0){
paths[i][j] = 1;
}else{
paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
}
}
}
return paths[m-1][n-1];
}
}
