数据结构与算法：动态规划

理论篇

动态规划问题

满足以下两个条件的问题被称为动态规划问题：

1. 具有最优子结构：问题的（最优）解可以由子问题的（最优）解推导出来，本质仍是递归。为了避免概念复杂化，我仍然使用”递推“概念的代替”最优子结构“或”状态转移方程“的概念；
2. 具有重叠子问题：不同子问题包含了重复的子子问题；

以最简单的0-1背包问题为例：

LintCode 92.0-1背包问题：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。

样例：4个物品[2, 3, 5, 7]，如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。

分析：每个物品只有放入或不放入两个状态，考虑以下具有一般意义的子问题：用i位置之前(包含i)的物品装入大小为k的背包最多能装下多少？我们用dp[k][i]来表示该子问题的解。通过讨论要不要将第i个物品放入，可以很容易得出dp的递推式：①如果不放入第i个物品，那么问题等价于将前i-1之前的物品放入k容量背包所能得到的最大解；②如果k>=A[i]，那么可以将第i个物品放入背包，再加上i-1之前的物品放入剩下容量所能得到的最大解就是在这种情况下得到的最优解；如果k<A[i]那么无法将第i个物品放入容量为k的背包，问题转化为第一种情况；可以形式化地用以下状态转移方程来表示子问题的最优解间的递推关系：

$$\left\{\begin{matrix} \begin{align*} &dp[k][i]=max(dp[k][i-1], dp[k-A[i]][i-1]+A[i]) ,& \ if\ k\geqslant A[i]\ i\geqslant 1 \\ &dp[k][i]=dp[k][i-1] ,&if\ k<A[i] \ i \geqslant 1\\ &dp[k][i]=0\ if\ k<A[i]\ else\ A[i],&if\ i==0 \end{align*} \end{matrix}\right.$$

• 最优子结构：子问题的最优解dp[k][i]可以由规模更小的同类子问题通过递推求解；
• 重叠子问题：以上状态转移方程可以看出，不同子问题包含了重复的子子问题；

动态规划算法

动态规划思想本质上可以看做是一种”带记录的递推方法“，用空间换取时间避免对子问题的重复求解。同样以上述 0-1 背包问题为例，一般有三种思路来求解：

1. 暴力DFS：我们可以通过DFS遍历出所有可能的解，在从中选出最优解；因为每个物品都有两种状态，放入或不放入，时间复杂度接近$O(2^n)$；后面我们会看到，有许多剪枝方法可以大大降低DFS的时间复杂度，但是时间复杂度仍然是指数级的；
2. 普通的递归：通过做出递归树可以看出这种方式同样需要指数级时间复杂度；
3. 动态规划：普通的递归会重复求解相同的子问题，只需要在求解子问题的同时记录这些解，下次用到时直接读取，我们可以将时间复杂度降为$O(m*n)$

解决实际动态规划问题的关键在于构造出具有最优子结构的子问题，写出状态转移方程，然后用填表法求解：

1. 构造具有最优子结构的子问题（状态）：我们用dp[i,j,k…]代表子问题的最优解，参数i,j,k称为子问题的状态变量，参数的个数称为子问题的维数，按照维度不同可以将动态规划问题做如下划分：
   1. 零维dp：代表当前的最优解（如股票问题）
   2. 一维dp[i]：代表i之前/之后的最优解，或者以i结尾/开头的最优解
   3. 二维dp[i][j]：代表[i,j]范围内的最优解，或者以i,j为边界的最优解
2. 写出递推关系（状态转移方程）：有以下两点原因使得经常需要结合分治思想来讨论不同条件下的递推关系，具体分类条件要视具体问题而定
   1. 动态规划通常用于解决最优化问题和计数问题，意味着子问题的解是多种情况下的最优解或总和；
   2. 通常子问题本身并不具有递归性，通过分类讨论可以挖掘出子问题间潜在的递推关系
3. 填表求解：无论是带记录的递归还是自底向上的填表本质上都是一种填表操作，表的作用是可以在O(1)的时间复杂度读取已求解的子问题的解，常用来表示表的数据结构有：
   1. 数组：如果状态变量可以用连续的下标来表示，则可以用一维或多维数组来存储子问题的解
   2. 哈希表：如果状态变量不规则或者稀疏，则一般用哈希表来存储子问题的解

动态规划实现

动态规划算法通常有两种实现方式：

1. 带记录的递归：一种自顶向下按需求解子问题的方法，边界情况直接求解记录，否则按照状态转移方程转化为求子问题的解，每个子问题只会被求解并记录一次，如需重复求解子问题则只需从记录中读取；
2. 自底向上填表：一种自底向上地毯式的填表法，由边界情况开始，通过状态转移方程不断求解更大规模的子问题，直至整张表被填满；

以0-1背包问题为例：

# 带记录的递归
def backPack(self, m, A):
    n = len(A)
    dp = [[-1] * (n) for _ in xrange(m+1)]
    
    def solve(k,i):
        if dp[k][i] == -1:
            if i == 0:
                dp[k][i] = A[i] if k >= A[i] else 0
            elif k >= A[i]:
                dp[k][i] = max(solve(k,i-1), solve(k-A[i],i-1)+A[i])
            else:
                dp[k][i] = solve(k,i-1)
        return dp[k][i]
        
    return solve(m,n-1)
    
# 自下向上填表法
def backPack(self, m, A):
    """
    这里使用了一个小技巧来处理边界：使用额外的空间dp[*][-1]来将边界情况统一到递推式中    
    """
    n = len(A)
    dp = [[0] * (n+1) for _ in xrange(m+1)]
    for k in xrange(m+1):
        for i in xrange(n):
            if k >= A[i]:
                dp[k][i] = max(dp[k][i-1], dp[k-A[i]][i-1]+A[i])
            else:
                dp[k][i] = dp[k][i-1]
    return dp[m][n-1]

# 这里通过两种常见的技巧来优化空间复杂度，核心代码只有 5 行：
#   1. 滚动数组：第 i 列只依赖于 第 i-1 列，可以使用一个临时数组存储上一次迭代的数据；
#   2. 逆序更新：第 k 行只依赖于更小行中的值，可以逆序更新每行的值，进一步省去了滚动数据；
def backPack(self, m, A):
    dp = [0] * (m + 1)
    for i in range(len(A)):
        for j in range(m, A[i]-1, -1):
            dp[j] = max(dp[j], dp[j-A[i]]+A[i])
    return dp[-1]
    

实践篇

背包问题

• 普通0-1背包问题
• 大容量0-1背包问题
• 部分背包问题
• 完全背包问题

class Solution:
    """
    @param s: The capacity of backpack
    @param v: The value of goods 
    @param c: The capacity of goods
    @return: The answer
    """
    def getMaxValue(self, s, v, c):
        n = len(v)
        dp = [[0] * (n+1) for _ in xrange(s+1)]
        
        for x in xrange(s+1):
            for j in xrange(n):
                if c[j] <= x:
                    dp[x][j] = max(dp[x-c[j]][j-1]+v[j],dp[x][j-1])
                else:
                    dp[x][j] = dp[x][j-1]
        
        return dp[s][n-1]


class Solution:
    """
    @param s: The capacity of backpack
    @param v: The value of goods 
    @param c: The capacity of goods
    @return: The answer
    """
    def getMaxValue(self, s, v, c):
        n = len(v)
        dp = [0] * (s+1)
        
        for i in xrange(n):
            for x in xrange(s,0,-1):
                if c[i] <= x:
                    dp[x] = max(dp[x], dp[x-c[i]]+v[i])
        
        return dp[s]
        
from collections import deque
class Solution:
    """
    @param s: The capacity of backpack
    @param v: The value of goods 
    @param c: The capacity of goods
    @return: The answer
    """
    def getMaxValue(self, s, v, c):
        m = len(v)
        vc = [(v[i],c[i]) for i in xrange(m)]
        vc.sort(key=lambda x:1.*x[1]/x[0])
        n = len(vc)
        self.max_v = 0
        
        def bound(i, in_v, in_c):
            """
            遍历到vc[i]时，袋中总价值in_v，总体积in_c，返回在此基础上可能达到的最大价值上界
            """
            while i < n and in_c + vc[i][1] <= s:
                in_v += vc[i][0]
                in_c += vc[i][1]
                i += 1
            if i < n and in_c < s:
                in_v += vc[i][0] * 1.0 / vc[i][1] * (s - in_c)
            return in_v 
        
        def dfs(i, in_v, in_c):
            """
            深度遍历获取可能的最大价值，收集-剪枝-前进-后退
            """
            if i < n and bound(i, in_v, in_c) > self.max_v:
                if in_c + vc[i][1] <= s:
                    self.max_v = max(self.max_v, in_v+vc[i][0])
                    if i < n - 1:
                        dfs(i+1, in_v+vc[i][0], in_c+vc[i][1])
                if i < n - 1:
                    dfs(i+1, in_v, in_c)
 

        dfs(0, 0, 0)
        return self.max_v
         
import bisect
class Solution:
    """
    @param s: The capacity of backpack
    @param v: The value of goods 
    @param c: The capacity of goods
    @return: The answer
    """
    def getMaxValue(self, s, v, c):
        """
        折半枚举
        """
        n = len(v)
        k = n / 2
        
        # 枚举前半部分
        left = []
        for i in xrange(1 << k):
            lc = lv = 0
            for j in xrange(k):
                if (i >> j) & 1:
                    lc += c[j]
                    lv += v[j]
            left.append((lc, lv))
        
        # 压缩前半部分,去除多余的使得left中的元素满足(a,b),(c,d)，a<=c, b<d
        left.sort()
        bag = 1
        for i in xrange(1 << k):
            if i and left[i][1] > left[bag-1][1]:
                left[bag] = left[i]
                bag += 1
        
        # 枚举后半部分
        res = 0
        for i in xrange(1 << (n-k)):
            if i > 10000:
                print i
            rc = rv = 0
            for j in xrange(n-k):
                if (i >> j) & 1:
                    rc += c[k+j]
                    rv += v[k+j]
            # 在前半部分二分查找rc的残差
            if rc <= s:
                idx = bisect.bisect_left(left[:bag], (s-rc,float('inf'))) - 1
                res = max(res, left[idx][1] + rv)
            
        return res

股票买卖问题

多阶段决策最优解的典型范例。

[LeetCode 121] 一次买卖股票最大利润

• 问题：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。
• 思路:每天结束可能有三种状态：可买、已买、已卖，以下为三者状态方程，最终返回三者中的最大值。

可买 = 0
已买 = max(已买，-p)
已卖 = max(已卖，已买+p)

• 代码：

def maxProfit(self, prices):
    for_buy, bought, sold = 0, float('-inf'), float('-inf')
    for p in prices:
        for_buy, bought, sold = 0, max(bought, for_buy-p), max(sold, bought+p)
    return max(for_buy, sold)

[LeetCode 123] 两次以内买卖股票最大利润

• 问题：限定最多可以完成两笔交易
• 思路：每天的状态可能是：未买、已买1次、已卖1次、已买2次、已卖2次，以下为状态转移方程，最终返回所有状态下的最大利润

未买 = 0
已买1次 = max(已买1次，未买-p)
已卖1次 = max(已卖1次，已买1次+p)
已买2次 = max(已买2次，已卖1次-p)
已卖2次 = max(已卖2次，已买2次+p)

• 代码：

def maxProfit(self, prices):
    for_buy, bought1, sold1, bought2, sold2 = 0, float('-inf'), float('-inf'), float('-inf'), float('-inf')
    for p in prices:
        for_buy, bought1, sold1, bought2, sold2 = 0, max(bought1, -p), max(sold1, bought1+p), max(bought2, sold1-p),max(sold2, bought2+p)
    return max(for_buy, bought1, sold1, bought2, sold2)

[LeetCode 122] 无限次买卖股票最大利润

• 问题：去掉121问题中一次购买的限制，但是你必须在再次购买前出售掉之前的股票
• 思路：无限次购买，可将可买状态与已卖状态合并为可买状态，状态转移方程为：

可买 = max(可买，已买+p)
已买 = max(已买，可买-p)

• 代码：

def maxProfit(self, prices):
    bought, for_buy = float('-inf'), 0
    for p in prices:
        bought, for_buy = max(bought, for_buy-p), max(for_buy, bought+p)
    return for_buy

[LeetCode 714] 无限次买卖股票含手续费最大利润

• 问题：你可以无限次地完成交易，但是你每次交易都需要付手续费
• 分析：每天结束可能有两种状态：已买、可买，二者状态转移方程为：

已买 = max(已买，可买-p)
可买 = max(可买，已买+p-fee)

• 代码：

def maxProfit(self, prices, fee):
    for_buy, bought = 0, float('-inf')
    for price in prices:
        bought, for_buy = max(bought, for_buy - price), max(for_buy, bought + price - fee)
    return max(bought, for_buy)

[LeetCode 309] 无限次买卖股票含冷冻期最大利润

• 问题：卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
• 思路：每天结束可能有三种状态：可买、已买、冷冻期，状态转移方程为:

可买 = max(可买，冷冻期)
已买 = max(已买，可买-p)
冷冻期 = 已买+p

• 代码：

def maxProfit(self, prices):
    for_buy, bought, freeze = 0, float('-inf'), float('-inf')
    for p in prices:
        for_buy,bought,freeze = max(for_buy,freeze),max(for_buy-p,bought),bought+p
    return max(for_buy, bought, freeze)

[LeetCode 188] 最多k次买卖最大利润

• 问题：最多可以完成 k 笔交易
• 思路：滚动数组+无限次买卖。如果2k >=n则转化为无限次买卖；否则每天结束的状态有2k+1种，未买，已买1次、已卖1次、…已买k次、已卖k次，用一个状态数组dp表示，以下为状态转移方程，利用滚动数组更新上述状态，最终返回数组最大值。

未买 = 0
已买i次 = max(已买i次，已卖i-1次-p)
已卖i次 = max(已卖i次，已买i次+p)
```    
- 代码：

```python
def maxProfit(self, k, prices):
    n = len(prices)
    if 2 * k >= n:
        bought, for_buy = float('-inf'), 0
        for p in prices:
            bought, for_buy = max(bought, for_buy-p), max(for_buy, bought+p)
        return for_buy
    else:
        dp = [0] + [float('-inf')] * (2*k)
        for p in prices:
            for i in xrange(1, 2*k+1):
                if i & 1:
                    dp[i] = max(dp[i], dp[i-1]-p)
                else:
                    dp[i] = max(dp[i], dp[i-1]+p)
        return max(dp)

• 分析：时间复杂度为O(kn)，空间复杂度为O(k)

其他问题

• 求和问题
• 子序列问题
• 回文子串问题
• DFS问题