【论如何定义dp table】 2020-10-04（未允禁转）
2020-10-05 本文已影响0人
9_SooHyun
关于dp基础，见dp基础
1. dp table = 当前问题规模 + 当前问题状态
dp问题，首先要定义出dp table，然后找到对应的状态转移方程。如何定义dp table成为解决问题的前提
如何定义dp table，
- 对于简单的单状态dp问题，我们依靠经验、直觉、灵感等，定义出合适的dp table不会有很大的困难。因为状态单一，dp table仅仅用来刻画问题规模的变化
- 对于多状态dp问题，如果没有一个普适的思路，那么定义dp table也将变得困难，因为dp table既要描述问题规模，也要描述问题所在的状态，这样一来，相应的dp table也是高维的，这时经验、直觉、灵感就难以解决问题
归纳上面的分析，实际上，不管是多状态dp还是单状态dp，dp table都要正确描述2个方面的信息，【当前问题规模 + 当前问题状态】。只是单状态dp的状态单一，可以省略不去描述
dp = dp[scale][status]
[scale]可以是一维的，也可以是二维的，三维的，等等，要看具体问题。即
dp[i][status] or dp[i][j][status] or etc
[status]也可以是一维的（单状态），也可以是二维的，三维的，等等（多状态）。即
dp[scale][status1] or dp[scale][status1][status2] or etc
2. 实例
leetcode中，股票系列问题是很好的实例
本文也是参考股票问题系列通解（转载翻译）和Most consistent ways of dealing with the series of stock problems形成
股票系列的通用问题是，
- 给出一个数组prices，表示一只股票每一天的价格。求最多交易k次能够获得的最大利润
- 买卖规则：每次买入该股票时，必须未持有任何数量的股票。买卖一次视为一次交易
解：
首先直观感受，当前能够获得的最大利润，必然和这之前股票的买卖情况相关，这里面应该存在一个不同规模间的状态转移关系，可以dp。而dp就是暴力，多了备忘录的暴力，暴力就是尝试每一种买卖情况，总是可以得答案的。这么想下来，dp基本上能做
- 定义dp table，找scale和status。scale就是一维的[i]，表示到第i天的最大利润；status，这里有两类状态，分别是
status1 -> k，表示当天操作后至多交易了k次，取值[0, k] status2 -> stock_keep，表示当天操作后股票持有情况，取值[0,1]，1持有，0不持有这样，dp table就是如下形式
dp[scale][status1][status2] = dp[i][k][stock_keep]
- 状态转移方程
以买进作为一次交易的标志，则
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
以卖出作为一次交易的标志，则
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k - 1][1] + prices[i])
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])
- 确定dp的base
base = 各规模的初始状态对应的最优dp值 + 最小规模的所有状态对应的最优dp值
- 返回dp[-1][k][0]
leetcode122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 考虑把price缩小一点，就变成一个子问题，不同规模的问题可以转移。因此可以dp
# dp[scale][status] -> dp[i][status]，表示在第i天时最后一次操作是buy/sell的最大利润
l = len(prices)
if l == 0 or l == 1:
return 0
dp = [[0, 0] for i in range(l)]
# 初始化dp
dp[0][0] = -prices[0]
# 填充dp
for i in range(1, l):
# 状态转移方程
dp[i][0] = max(dp[i-1][1] - prices[i], dp[i-1][0]) # buy
dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]) # sell
# print(dp)
return max(dp[-1])
leetcode 188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
以买进作为一次交易的标志
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
def getMax(nums):
res = 0
base = nums[0]
for i in range(1, len(nums)):
if nums[i] >= base:
res += (nums[i] - base)
base = nums[i]
return res
l = len(prices)
# 如果k超过了prices长度的一半，直接简化成getMax(prices)
if k > l // 2:
return getMax(prices)
### dp 代码 ###
# 以买进作为一次交易的标志
# 3维dp
dp = [[[0 for i in range(2)] for j in range(k+1)] for _ in range(l)]
# 初始化dp base
# 【各规模的初始状态】
for i in range(l):
dp[i][0][0] = 0
dp[i][0][1] = 0
# 【最小规模的所有状态】
for i in range(1, k+1):
dp[0][i][0] = 0
dp[0][i][1] = -prices[0]
for i in range(1, l):
for kk in range(1, k+1):
dp[i][kk][0] = max(dp[i - 1][kk][0], dp[i - 1][kk][1] + prices[i])
dp[i][kk][1] = max(dp[i - 1][kk][1], dp[i - 1][kk - 1][0] - prices[i])
return dp[-1][k][0]
### dp 代码 ###
以卖出作为一次交易的标志
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
def getMax(nums):
res = 0
base = nums[0]
for i in range(1, len(nums)):
if nums[i] >= base:
res += (nums[i] - base)
base = nums[i]
return res
l = len(prices)
# 如果k超过了prices长度的一半，直接简化成getMax(prices)
if k > l // 2:
return getMax(prices)
### dp 代码 ###
# 以卖出作为一次交易的标志
# 3维dp
dp = [[[0 for i in range(2)] for j in range(k+1)] for _ in range(l)]
# 初始化dp base
# 【各规模初始状态】
for i in range(l):
dp[i][0][0] = 0
dp[i][0][1] = -min(prices[:i+1])
# 【最小规模所有状态】
for i in range(1, k+1):
dp[0][i][0] = 0
dp[0][i][1] = -prices[0]
# 状态转移
for i in range(1, l):
for kk in range(1, k+1):
dp[i][kk][0] = max(dp[i - 1][kk][0], dp[i - 1][kk - 1][1] + prices[i])
dp[i][kk][1] = max(dp[i - 1][kk][1], dp[i - 1][kk][0] - prices[i])
return dp[-1][k][0]
### dp 代码 ###
