力扣 62 不同路径

题意：给定一个二维数组，找出从top left到bottom right的所有路径

思路：动态规划，遍历每一行，dp[i]表示某一行的节点i的所有可能路径总数，递推公式dp[i] = dp[左边的路径总数] + dp[上边的路径总数]

思想：动态规划

复杂度：时间O（m^n)，空间O(n)

class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 0 || n ==0)
            return 0;
        int[] dp = new int[n];
        for(int i=0;i<n;i++) {
            dp[i] = 1;
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[n-1];
    }
}