原題鏈接在這里：https://leetcode.com/problems/unique-paths/

題目：

A robot is located at the top-left corner of a?m?x?n?grid (marked 'Start' in the diagram below).?

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:?m?and?n?will be at most 100.

題解：

DP問題.需保存歷史數據為走到當前格子的不同路徑數，用二維數組dp保存。?

更新當前點dp[i][j]為上一行同列dp[i-1][j]的值 + 本行上一列dp[i][j-1]的值，因為走到上一行同列的值想走到當前格都是往下走一步，左邊同理。

初始化是第一行和第一列都是1.

答案是dp[m-1][n-1].

Time Complexity: O(m*n). Space: O(m*n).

AC Java:

1 public class Solution { 2 public int uniquePaths(int m, int n) { 3 if(m == 0 || n == 0){ 4 return 0; 5 } 6 int [][] dp = new int[m][n]; 7 for(int i = 0; i<m; i++){ 8 dp[i][0] = 1; 9 } 10 for(int j = 0; j<n; j++){ 11 dp[0][j] = 1; 12 } 13 for(int i = 1; i<m; i++){ 14 for(int j = 1; j<n; j++){ 15 dp[i][j] = dp[i-1][j] + dp[i][j-1]; 16 } 17 } 18 return dp[m-1][n-1]; 19 } 20 }

存儲歷史信息可以用一維數組完成從而節省空間。生成一個長度為n的數組dp, 每次更新dp[j] += dp[j-1], dp[j-1]就是同行前一列的歷史結果，dp[j]為更新前是同列上一行的結果，所以dp[j] += dp[j-1]就是更新后的結果。

Note:外層loop i 從0開始，dp[0] = 1, 相當于初始了第一列，所以i=0開始要初始第一行

Time Complexity: O(m*n). Space: O(n).

?

1 class Solution { 2 public int uniquePaths(int m, int n) { 3 if(m == 0 || n == 0){ 4 return 0; 5 } 6 7 int [] dp = new int[n]; 8 for(int j = 0; j<n; j++){ 9 dp[j] = 1; 10 } 11 12 for(int i = 1; i<m; i++){ 13 for(int j = 1; j<n; j++){ 14 dp[j] = dp[j] + dp[j-1]; 15 } 16 } 17 18 return dp[n-1]; 19 } 20 }

有進階版題目Unique Paths II.

轉載于:https://www.cnblogs.com/Dylan-Java-NYC/p/4824960.html

總結

以上是生活随笔為你收集整理的LeetCode Unique Paths的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。