Algorithm of DP: Basic Problems

weigaochen 11/23/2021 algorithm

🚑🚑🚑 针对动态规划，本文主要讲述动态规划基础问题及求解，包括：

记忆化搜索
TODO

# 记忆化搜索

# 概览

记忆化搜索和 DP 是有很多相似之处的，所以把记忆化搜索放在 DP 里面进行研究。

总的来说，我们写记忆化搜索算法的步骤大致为：

使用 BFS 记忆化：
1. 写出这道题的暴力搜索程序（如 DFS）
2. 将这个 DFS 改写城 “无需外部变量” 的 DFS
3. 添加记忆化数组
使用状态转移方程记忆化：
1. 把这道题目的 DP 和方程写出来
2. 根据它们写出 DFS 函数
3. 添加记忆化数组

其优点在于：

避免搜索到无用状态

其缺点在于：

不能滚动数组
有些优化较难
效率较低但是不至于 TLE

有时候会觉得，这个记忆化搜索和 DFS 很像，也有点背包的感觉，以后再好好研究一下。

2021 年 11 月 24 日：就目前理解来说，这是一种很垃圾的算法。

# LC638 大礼包

638. 大礼包 (opens new window)

这道题目可以利用记忆化搜索的方式去求解。

首先按照例子解释一下这个用例：

price = [2, 5] // A,B 对应的价格

special = [[3, 0, 5], [1, 2, 10]] // 表示折扣，3A 0B 的大礼包价格是 5

needs = [3, 2] // 需要买的总的数量

我们该怎么合理使用大礼包呢？

按照记忆化搜索的思路，我们首先过滤掉无用的状态，即过滤掉不需要计算的大礼包，可以分几种情况来判断哪些大礼包是我们不需要的：
- 根据题目要求「不能购买超出购物清单指定数量的物品」，如果大礼包里面的所有物品加起来超过我们要买的物品总数了，那么这个大礼包不能要；
- 大礼包不划算则不选这个大礼包（不划算指的是我单独买这些物品，下来大礼包反而贵了）
- 大礼包内不包含我们要买的物品，也不能买
以上的条件就是我们记忆化搜索时可以用来筛选的条件。
根据题目要求，我们可以写出大致的状态转移方程。
- 我们用 dp 表示满足购物清单 needs 需要的最小花费
- 我们思考满足购物清单 needs 的最后一次购买，其可以分为两种情况：
  1. 购买大礼包
  2. 不购买大礼包
- 我们如果购买大礼包的时候，可以遍历每一个大礼包，表示第个大礼包的价格，表示大礼包中的物品清单，表示购物清单减去第个大礼包中包含的物品清单后剩余的物品清单。

先附上官方题解，这个题解目前还有很多的疑问点：

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

Chener丶

Choose mode

Algorithm of DP: Basic Problems

Algorithm of DP: Basic Problems

# 记忆化搜索

# 概览

# LC638 大礼包

# P1048 [NOIP2005 普及组] 采药

# LC329 矩阵中的最长递增路径