114. Unique Paths

Description

A robot is located at the top-left corner of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

m and n will be at most 100.

Example

Example 1:

Input: n = 1, m = 3

Output: 1

Explanation: Only one path to target position.

Example 2:

Input:  n = 3, m = 3

Output: 6

Explanation:

D : Down

R : Right

1) DDRR

2) DRDR

3) DRRD

4) RRDD

5) RDRD

6) RDDR

思路：

坐标型动态规划，当前点的路径数等于前序点路径数之和，这里有用hashmap和list实现的两种方法，需要注意初始化时的浅拷贝问题。

代码：