概念

数组是最常见的数据结构之一，现在对数组的下标进行特殊处理，使每一次操作仅保存有用信息，新的元素不断循环更新，看上去数组的空间被滚动的利用，此模型成为滚动数组。其主要目的是压缩存储，一般在动态规划问题中使用。

例题

一、0-1背包问题

n和物品x1,x2,...,xn的价值和重量分别为：
v1,v2,...,vn
w1,w2,...,wn
现有一个背包，其最大载重量为m，求如何装包是所装物品的价值和最大？

构造二维动态数组
  • 构造：
    构造dp[n][m]数组，从n个物品中选择，装到m容量的包中的最大价值和。
  • base case:
    dp[0][j] = 0
    dp[i][0] = 0
  • 状态转移：
    for i in range(1,n):
  for j in range(1,m):
      if j-w[i]>=0:
          dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
     else:
          dp[i][j] = dp[i-1][j]
滚动数组
  • 从推到过程中可以看出，第i阶段的状态值只与i-1阶段有关。所以可以将[0...n][0...m]改为[0...m]
  • 构造：
    构造dp[m]数组
  • 状态转移：
    for i in range(n):
  for j in range(m-1,-1,-1):
      if j-w[i]>0:
          dp[j] = max(dp[j],dp[j-w[i]]+v[i])
    注意：此处需要逆序处理，这样可以保证在计算dp[j]时，公式dp[j]=max(dp[j],dp[j-w[i]]+v[i])中等号右边的dp[j]和dp[j-w[i]]+v[i]保存的时dp[i-1][j],dp[i-1][j-w[i]]+v[i]的值。

二、不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

# 方法一：回溯，超时
 def uniquePathsWithObstacles(obstacleGrid) :
    if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1: return 0
    if not obstacleGrid: return 0
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    res = 0
    def backtrack(i,j):
        nonlocal res
        if i == m-1 and j == n-1:
            print(res)
            res += 1
            return
        if i<0 or i>=m or j<0 or j>=n or obstacleGrid[i][j] == 1:
            return
        backtrack(i+1,j)
        backtrack(i,j+1)
    backtrack(0,0)
    return res
'''
方法二：动态规划
dp[i][j]:表示从起点到(i,j)的路径条数
状态转移：
若obstacleGrid[i][j] == 1: dp[i][j] = 0
若obstacleGrid[i][j] == 0: dp[i][j] = dp[i-1][j]+dp[i][j-1]
执行用时：44 ms, 在所有 Python3 提交中击败了60.14%的用户
内存消耗：13.8 MB, 在所有 Python3 提交中击败了14.29%的用户
'''
def uniquePathsWithObstacles(obstacleGrid):
    if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1: return 0
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    dp = [[0]*n for _ in range(m)]
    #base case:
    # 第一列，若该位置可以到达，则到达该位置路径条数为1，否则该位置及其后面的位置无法到达
    for i in range(m):
        if obstacleGrid[i][0] == 1:
            break
        dp[i][0] = 1
    # 第一行，同上
    for j in range(n):
        if obstacleGrid[0][j] == 1:
            break
        dp[0][j] = 1
    # 状态转移
    for i in range(1,m):
        for j in range(1,n):
            if obstacleGrid[i][j] == 1:
                continue
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
    return dp[-1][-1]
'''
方法三：采用滚动数组优化代码，提高空间利用率
'''
def uniquePathsWithObstacles(obstacleGrid):
    if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1: return 0
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])
    dp = [0 for _ in range(n)] # n列
    dp[0] = 0 if obstacleGrid[0][0] == 1 else 1
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0 # 重要
                continue
            elif j >= 1:
                dp[j] += dp[j-1]
    return dp[-1]

三、最大子序列和

状态压缩，应该不属于滚动数组范围，但是还是记录一下。。。

给定一个数组nums[n1,n2,...nn]，求最大子序列和。

# 方法一：枚举子序列的左端点，扫描右端点
def maxSubArray(nums):
    n = len(nums)
    res = -float('inf')
    for i in range(n):
        sum = 0
        for j in range(i,n):
            sum += nums[j]
            res = max(res,sum)
    return res

# 方法二：一维数组
def maxSubArray(nums):
    n = len(nums)
    dp = [nums[i] for i in range(n)]
    for i in range(1,n):
        dp[i] = max(nums[i],dp[i-1]+nums[i])
    return max(dp)

方法三：压缩数组
def maxSubArray(nums):
    n = len(nums)
    res = -float('inf')
    dp = nums[0] 
    for i in range(1,n):
        dp = max(nums[i],dp+numd[i])
        res = max(res,dp)
    return res

leetcode 221 -> 四、最大正方形 ***

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

剑指offer 1162 -> 五、地图分析

leetcode 46 -> 六、把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法.

输入: 12258 输出: 5

解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

# 法一：递归
def trans(num):
    if num < 10 : return 1
    if num%100<26 and num%100>9:
        # 后两位在10-25之间
        return trans(num//100)+trans(num//10)
    else:
        return trans(num//10)

# 法二：动态规格
'''
动态规划
dp[i] 表示以第i位结尾的数字可以翻译的方案数量
      此时考虑第i位和第i-1位组成的数是否在10-25之间，若在：dp[i] = dp[i-2]+dp[i-1]
      若不在：dp[i] = dp[i-1] -> (单独翻译)
'''
def translate(num):
    nums = str(num)
    dp = [0 for _ in range(len(nums))]
    dp[0] = 1
    dp[1] = 2 if 10 <= int(nums[:2]) <=25 else 1
    for i in range(2,len(nums)):
        if 10 <= int(nums[i-1:i+1]) <= 25:
            dp[i] = dp[i-2] + dp[i-1]
        else:
            dp[i] = dp[i-1]
    return dp

# 法三：滚动数组
'''
因为dp[i]只与dp[i-1]和dp[i-2]有关
则可以利用滚动数组进行空间压缩
dp0,dp1 充当dp[i-2],dp[i-1]
'''
def translate(num):
    if num<10: return 1
    nums = str(num)
    dp0 = dp1 = 1
    res = 0
    for i in range(1,len(nums)):
        if 10<=int(nums[i-1:i+1])<=25:
            res = dp0+dp1
        else:
            res = dp1
        dp0 = dp1
        dp1 = res
    return res

leetcode 70 -> 七、爬楼梯