"""
62.不同路径
解题思路：
创建二维的数组记录中间状态量
压缩之后其中的没有体现的一层循环其实代表着一层坐标

动态规划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:
    def uniquePaths(self, m: int, n: int) -> int:

        # 二维数组方式
        # dp = [[0] * n for i in range(m)]

        # for i in range(n):
        #     dp[0][i] = 1

        # for j in range(m):
        #     dp[j][0] = 1

        # for i in range(1, m):
        #     for j in range(1, n):
        #         dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # return dp[-1][-1]

        # 优化空间复杂度的方式
        dp = [1] * m
        print(dp)

        for j in range(1, n):
            for i in range(1, m):
                dp[i] = dp[i - 1] + dp[i]
                print(dp[i])

        return dp[-1]
