# LeetCode - 62. Unique Paths(不同的路径数量)(简单dp)
- 记忆化
- 二维dp
- 空间优化
***
#### [题目链接](https://leetcode.com/problems/unique-paths/description/)
> https://leetcode.com/problems/unique-paths/description/
#### 题目
![png](images/62_t.png)
这个题目和[最小路径和问题](https://github.com/ZXZxin/ZXBlog/blob/master/%E5%88%B7%E9%A2%98/LeetCode/DP/LeetCode%20-%2064.%20Minimum%20Path%20Sum(%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E5%92%8C).md)很类似。
## 1、记忆化
* **来到某个结点,因为只能往右边和下面走,所以一个位置`[i,j]`依赖的位置是`[i-1,j]`和`[i,j-1]`位置两个点之前的数量之和**;
* 所以我们把`[i,j]`看做是**终点**的话就得出下面的递归关系。
* 但是由于有重复的子问题,所以我们需要使用记忆化递归来优化。
图:
如果不记录重复子问题的话就会是`O(2^n)`;
```java
class Solution {
private int[][] dp;
public int uniquePaths(int m, int n) {
dp = new int[m + 1][n + 1];
return rec(m, n, m, n);
}
public int rec(int m, int n, int i, int j) {
if (i == 1 &&