滚动数组

在动态规划矩阵题中碰到了滑动数组的解法，能将空间复杂度从O(m n)降低到O(min(m,n))。并且不太能直观理解，故记录。

62.不同路径

个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

Solution1: 常规DP

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1]*n] + [[1] + [0]*(n-1) for _ in range(m-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]

Solution2: 用滚动数组代替二维数组

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        f = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                f[j] += f[j-1]
        return f[n-1]

可以理解为直接在一维数组上面更新数据，原普通DP是新的数据存储在下一行的数组里，因为之前的数据其实并不影响计算结果，可以直接覆盖。

举例：

1 1 1

1 2 3

1 3 6

其实就是对上一格和左一格数据的相加。