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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/62.-unique-paths.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.