> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/62.-unique-paths.md).

# 62. Unique Paths (2D-dp)

time complexity: O(n^2)

```java
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; // from left top corner
        for (int i = 0; i < n; i++) dp[0][i] = 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];
    }
}
```

from bottom...太不直覺了

```java
class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][n-1] = 1; // from button
        for (int i = 0; i < n; i++) dp[m-1][i] = 1;
        
        for (int i = m-1; i > 0; i--) {
            for (int j = n-1; j > 0; j--) {
                
                dp[i-1][j-1] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[0][0];
    }
}
```

a little optimization of the space, 1-D array

其實可以一行一行累加上來

![](/files/-M2GkZlLIcCmmGVVnbLn)

![](/files/-M2GkSiBBskyL3oHt-v1)

![](/files/-M2GmeoGn-OMxj9i0rFK)

因為只要計算紅匡的部分, 所以 這段 for loop 都從 1 開始

```java
        for (int i = 1; i < m; i++) { // row, from 1 start
            for (int j = 1; j < n; j++) { // column
                dp[j] += dp[j-1];
            }
        }
```

因為初始了index 0,  row 和 col

都為 11111,  應該說只需要初始 row index = 0的 11111

因為都用同一個一維陣列

所以當 row index = 1時

dp\[j], j   1 to n   都是 111111

要算 原本的dp\[1]\[1] ＝dp\[0]\[1] + dp\[1]\[0]

就只需要加上dp \[j-1], 也就是 dp\[j]+= dp \[j-1]    = ==  dp\[1]\[1]

因為dp\[j]本身就把dp\[0]\[1]的值帶下來了,&#x20;

只需要加上dp\[1]\[0]  (也就是dp\[j-1]

dp\[1]\[1] ＝dp\[0]\[1] + dp\[1]\[0]

dp\[1]\[1] = dp\[j] + dp \[j-1]

![](/files/-MBUPpbdGxwhsrlR-7AX)

```java
class Solution {
    public int uniquePaths(int m, int n) {
        int dp[] = new int[n]; // column size
        Arrays.fill(dp, 1); //fill each row to 1 first
        for (int i = 1; i < m; i++) { // row, from 1 start
            for (int j = 1; j < n; j++) { // from index 1 column
                dp[j] += dp[j-1]; //add pre column value
            }
        }
        return dp[n-1];
    }
}
```