class Solution(object): def uniquePaths(self, m, n): a =  * m for i in range (1,n): for j in range (1,m): a[j]=a[j-1]+a[j] return a[m-1]
Explanation: At each step i, a stores answers for n=i, m=j (in particular, if n=0 or m=0, the answer is always 1). As we increase n by 1, we can apply the recursive formula uniquePaths(m,n)=uniquePaths(m-1,n)+uniquePaths(m,n-1) to find the answer using already computed values. By using
a[j]=a[j-1]+a[j] for all j going from 0 up to m-1, we are actually implementing the same formula but within a single one-dimensional array.