'''
解题思路
动态规划5大步骤：

1.定义状态：即定义数据元素的含义，这里定义dp[i][j]为当前位置的路径数，i表示i列，j表示j行

2.建立状态转移方程：因为从题目要求中可以看出，机器人只能向右或向下移动。所以到达dp[i][j]就可能是经过dp[i-1][j]到达，
也可能是经过dp[i][j-1]到达。所以状态转移方程为：dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.设定初始值：通过状态转移方程可以看出，i和j下表要从1开始，否则会导致数组溢出异常。同时每一个位置点代表到达当前位置的路径条数，所以要设置最初的路径条数即dp[i][0]=1,dp[0][j]=1，即第一行，第一列值为1。

5.状态压缩：即优化数组空间，每次状态的更新只依赖于前一次的状态，优化一般作用于多维数组，观察是否可以将多维数组以一维数组来动态表示，即用一维数组来保存上次的状态。这道题的优化方法是存在的。具体看下面的代码解释。状态转移方程：dp[i] = dp[i-1] + dp[i]

6.选出结果：根据状态转移方程，求路径的总数，因此dp[-1][-1]表示的是到达最后位置的路径总条数。
'''
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 采用二位数组形式的动态规划
        # f[i][j]表示当前移动到的总次数，要求f[-1][-1]
        # 状态转移公式：f[i][j] = f[i-1][j]+f[i][j-1]
        # 初始值：每一步移动的次数可以看做横轴和纵轴的和，因此 f[i][0] = 1,f[0][j]=1
        # 运动的轨迹：要么往下，要么往左
        # 时间复杂度：O(m*n),空间复杂度：O(m*n)
        
        f = [[0]*n for zong in range(m)]
        for i in range(m):
            f[i][0] = 1
        for j in range(n):
            f[0][j] = 1
        for i in range(1,m):
            for j in range(1,n):
                f[i][j] = f[i-1][j]+f[i][j-1]
        return f[-1][-1]
        

        """优化空间复杂度为O(n)"""
        # 对二维矩阵进行压缩成一位数组,将最新生成的值覆盖掉旧的值,逐行求解当前位置的最新路径条数！
        # 实质：在于动态计算并替换当前位置下的路径数最新值
        # 状态转移公式变成：f[i] = f[i-1]+f[i]
        # 初始值： f = [1]*m,取横轴
        # f[-1]表示可能路径的总数
        # 空间复杂度：O(n),时间复杂度:O(m*n)

        f = [1]*m
        for j in range(1,n):
            for i in range(1,m):
                f[i] = f[i-1]+f[i]
        return f[-1]

'''
作者：yu-fa-tang-you-dian-tian
链接：https://leetcode-cn.com/problems/unique-paths/solution/dong-tai-gui-hua-ya-suo-shu-zu-you-hua-kong-jian-f/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''