> 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

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-M2DEFuPgE3UgSb11bWm%2F-M2GkZlLIcCmmGVVnbLn%2Fimage.png?alt=media\&token=a8fa5ac6-2226-488b-9030-7a6e5f7fbbc4)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-M2DEFuPgE3UgSb11bWm%2F-M2GkSiBBskyL3oHt-v1%2Fimage.png?alt=media\&token=e92cc24b-babb-4135-88d6-504a27bb3611)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-M2DEFuPgE3UgSb11bWm%2F-M2GmeoGn-OMxj9i0rFK%2Fimage.png?alt=media\&token=c156463f-e430-457e-bc6e-27a6f9de8e9b)

因為只要計算紅匡的部分, 所以 這段 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]

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MBNszLnNIOtO1Y4AVXN%2F-MBUPpbdGxwhsrlR-7AX%2Fimage.png?alt=media\&token=d8ab0439-bcc0-4e47-a523-3e5b0facd125)

```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];
    }
}
```