Algorithm of DP: Basic Problems
🚑🚑🚑 针对动态规划,本文主要讲述动态规划基础问题及求解,包括:
- 记忆化搜索
- TODO
# 记忆化搜索
# 概览
记忆化搜索和 DP 是有很多相似之处的,所以把记忆化搜索放在 DP 里面进行研究。
总的来说,我们写记忆化搜索算法的步骤大致为:
- 使用 BFS 记忆化:
- 写出这道题的暴力搜索程序(如 DFS)
- 将这个 DFS 改写城 “无需外部变量” 的 DFS
- 添加记忆化数组
- 使用状态转移方程记忆化:
- 把这道题目的 DP 和方程写出来
- 根据它们写出 DFS 函数
- 添加记忆化数组
其优点在于:
- 避免搜索到无用状态
其缺点在于:
- 不能滚动数组
- 有些优化较难
- 效率较低但是不至于 TLE
有时候会觉得,这个记忆化搜索和 DFS 很像,也有点背包的感觉,以后再好好研究一下。
2021 年 11 月 24 日:就目前理解来说,这是一种很垃圾的算法。
# LC638 大礼包
这道题目可以利用记忆化搜索的方式去求解。
首先按照例子解释一下这个用例:
price = [2, 5] // A,B 对应的价格
special = [[3, 0, 5], [1, 2, 10]] // 表示折扣,3A 0B 的大礼包价格是 5
needs = [3, 2] // 需要买的总的数量
我们该怎么合理使用大礼包呢?
按照记忆化搜索的思路,我们首先过滤掉无用的状态,即过滤掉不需要计算的大礼包,可以分几种情况来判断哪些大礼包是我们不需要的:
- 根据题目要求「不能购买超出购物清单指定数量的物品」,如果大礼包里面的所有物品加起来超过我们要买的物品总数了,那么这个大礼包不能要;
- 大礼包不划算则不选这个大礼包(不划算指的是我单独买这些物品,下来大礼包反而贵了)
- 大礼包内不包含我们要买的物品,也不能买
以上的条件就是我们记忆化搜索时可以用来筛选的条件。
根据题目要求,我们可以写出大致的状态转移方程。
我们用
dp
表示满足购物清单needs
需要的最小花费我们思考满足购物清单
needs
的最后一次购买,其可以分为两种情况:- 购买大礼包
- 不购买大礼包
我们如果购买大礼包的时候,可以遍历每一个大礼包,
表示第 个大礼包的价格, 表示大礼包中的物品清单, 表示购物清单 减去第 个大礼包中包含的物品清单后剩余的物品清单。
先附上官方题解,这个题解目前还有很多的疑问点:
class Solution:
def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
n = len(price)
filter_special = []
for sp in special:
# 比如在第一个例子中 i == 2
# 第二个条件表示大礼包是有优惠的,这时候我们选择该礼包
if sum(sp[i] for i in range(n)) > 0 and sum(sp[i] * price[i] for i in range(n)) > sp[-1]:
filter_special.append(sp)
@lru_cache(None)
def dfs(cur_needs):
# 在不购买大礼包的时候,购买购物清单中所有物品需要的花费
min_price = sum(need * price[i] for i, need in enumerate(cur_needs))
for cur_special in filter_special:
special_price = cur_special[-1]
nxt_needs = []
for i in range(n):
if cur_special[i] > cur_needs[i]:
# 不购买多于当前订单数量的物品
break
# 还剩下多少物品需要购买
nxt_needs.append(cur_needs[i] - cur_special[i])
# why, 如果上述遍历完成,满足数量条件,大礼包可以购买
if len(nxt_needs) == n:
min_price = min(min_price, dfs(tuple(nxt_needs)) + special_price)
return min_price
return dfs(tuple(needs))
对应的测试用例:
class Test(unittest.TestCase):
def setUp(self) -> None:
self.s = Solution()
def test_1(self):
# 折扣对应的价格
price = [2, 5]
# 表示折扣
special = [[3, 0, 5], [1, 2, 10]]
# 需要买的数量
needs = [3, 2]
res = self.s.shoppingOffers(price, special, needs)
self.assertEqual(14, res)
针对上面的疑点,我们可以参考背包问题中的经典背包问题,加深理解,然后再寻求求解方式。
# P1048 [NOIP2005 普及组] 采药
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
先给出测试代码:
class Test(unittest.TestCase):
def setUp(self) -> None:
self.s = Solution()
def test_1(self):
costs = [71, 69, 1]
values = [100, 1, 2]
res = self.s.solution(costs, values)
self.assertEqual(3, res)
我们在这个文章中研究记忆化搜索,所以考虑这个问题,首先按照暴力搜索的思路去解决。❌❌❌ 这个目前水平不足,后续待定。
我们给出求解这个问题的代码,按照经典的背包问题来求解。
import unittest
import numpy as np
class Solution:
def solution(self, weights, values, size):
if not size:
return 0
n = len(weights)
# 我们定义 dp 数组 dp[i][w], 对于前 i 个物品,当前背包容量为 w,可以装的最大价值是 dp[i][w]
# dp = [[0] * (size + 1) for _ in range(n)]
dp = np.zeros(shape=(n, size + 1))
# 循环中遍历物品
for i in range(1, n):
# 内层循环遍历背包容量
# for j in range(size + 1) 等同
for j in range(size, weights[i] - 1, -1):
# 当前背包装不下
if weights[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])
return dp[n - 1][size]
一维 DP 套用公式的解法:
def solution2(self, weights, values, size):
if not size:
return 0
# 我们拿容量去定义 dp
dp = [0] + [0] * size
# 按照背包问题的套路,遍历物品
for idx, weight in enumerate(weights):
for i in range(size, weight - 1, -1):
dp[i] = max(dp[i], dp[i - weight] + values[idx])
return dp[-1]
# LC329 矩阵中的最长递增路径
329. 矩阵中的最长递增路径 (opens new window)
- 由于同一个单元格对应的最长递增路径的长度是固定不变的,因此可以使用记忆化的方法进行优化;
- 用矩阵作为缓存矩阵,已经计算过的单元格的结果存储到缓存矩阵中。(在 python 中,可以直接使用
@lru_cache(None)
, 实现较为简单)
记忆化搜索实现如下:
class Solution:
def __init__(self, *args, **kwargs):
self.dirs = [
[0, 1], [1, 0], [0, -1], [-1, 0]
]
self.m = None
self.n = None
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
self.m = len(matrix)
self.n = len(matrix[0])
ans = 0
memo = [[0] * self.n for _ in range(self.m)]
def dfs(i, j):
if memo[i][j] != 0:
return memo[i][j]
memo[i][j] = 1
for d in self.dirs:
x, y = d[0] + i, d[1] + j
if 0 <= x < self.m and 0 <= y < self.n and matrix[x][y] > matrix[i][j]:
memo[i][j] = max(memo[i][j], dfs(x, y) + 1)
return memo[i][j]
for i in range(self.m):
for j in range(self.n):
if memo[i][j] != 0:
ans = max(ans, memo[i][j])
else:
ans = max(ans, dfs(i, j))
return ans