动态规划

code

public int uniquePaths(int m, int n) {
        int[] memo = new int[n];
        //第一行初始化为1
        Arrays.fill(memo,1);
        //从第2行开始更新
        for(int i=1;i<m;i++)
            //更新该行中的值
            for(int j=1;j<n;j++)
                //上边的元素加上左边的元素
                memo[j]+=memo[j-1];
        return memo[n-1];
}
//time  O(m*n)
//space  O(n)