系列：動(dòng)態(tài)規(guī)劃
語言：java
難度：中等
題目來源：Leetcode62. 不同路徑開啟動(dòng)態(tài)規(guī)劃章節(jié)了??！歡迎您在留言和我一起完成每日打卡，以后每天8點(diǎn)半前發(fā)布每日一題。
原題鏈接：Leetcode62. 不同路徑
題目
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。
問總共有多少條不同的路徑？
示例 1:
示例 2:
輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
示例 3:
輸入：m = 7, n = 3
輸出：28
示例 4:
輸入：m = 3, n = 3
輸出：6
約束條件：
1 <= m, n <= 100
題目數(shù)據(jù)保證答案小于等于 2 * 109
思路：
分析：動(dòng)規(guī)五部曲。
1.確定dp[i][j]含義：一個(gè)二維數(shù)組，表示到達(dá)i,j這個(gè)位置的路徑有多少種
2.確定遞推公式：因?yàn)槊看沃荒芟蛳潞拖蛴?，所以第dp[i][j]的位置只能由dp[i-1][j]（向下的路徑方法）和dp[i][j-1]（向右的路徑方法）合起來組成，dp[i][j] = dp[i-1][j]+dp[i][j-1];
3.初始化dp數(shù)組。對于dp[i][0]和dp[0][i]只有一種情況，表示向右和向下只有一種方式。所以規(guī)定他們都為1；
4.確定遍歷順序。 因?yàn)榈趇，j位置處的數(shù)只能有上面和左面的數(shù)推出，所以需要從左到右進(jìn)行遍歷，即一行一行從左到右進(jìn)行遍歷。
代碼實(shí)現(xiàn)：文章來源：http://www.zghlxwxcb.cn/news/detail-421478.html
class Solution {
public int uniquePaths(int m, int n) {
int [][] dp = new int[m][n];
for(int i =0;i<m;i++){
dp[i][0] = 1;
}
for(int j=0;j<n;j++){
dp[0][j] = 1;
}
for(int i =1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
感謝您的閱讀，希望對您有所幫助。關(guān)注我，完成每日算法自律打卡，什么時(shí)候開始都不晚??！文章來源地址http://www.zghlxwxcb.cn/news/detail-421478.html
到了這里，關(guān)于leetcode每日一題：62. 不同路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
