pcw0118#ZXBlog#LeetCode-62.Unique Paths(不同的路径数量)(简单dp)1

# LeetCode - 62. Unique Paths(不同的路径数量)(简单dp) - 记忆化 - 二维dp - 空间优化 *** #### [题目链接](https://leetcode.com/problems/unique-paths/description/) > https://leetcode.com/problems/unique-paths/description/ #### 题目  这个题目和[最小路径和问题](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 &&