数据结构与算法实例详解--动态规划、数组篇

动态规划（Dynamic Programming，DP）是一种求解优化问题的算法设计技巧，主要用于解决具有重叠子问题和最优子结构性质的问题。动态规划通过将复杂问题分解为更小的子问题，避免了重复计算，从而提高了算法的效率。动态规划是一种高效的算法设计技术，它利用子问题的解来构建更大问题的解。在实现动态规划时，数组是一个重要的工具，用于存储中间结果并实现状态转移。这种方法在许多问题中，如最短路径、背包问题和字符串匹配等，广泛应用。

动态规划的核心概念

1. 重叠子问题：问题可以分解为子问题，且这些子问题会多次出现。例如，在求斐波那契数列时，F(n) = F(n-1) + F(n-2)，F(n-1)和F(n-2)会被多次计算。

2. 最优子结构：一个问题的最优解由其子问题的最优解构成。也就是说，求解一个问题的最优解，可以通过求解其子问题的最优解来实现。

动态规划的基本步骤

1. 定义状态：确定需要用什么状态来表示子问题的解。

2. 状态转移方程：找出状态之间的关系，构建递推关系。

3. 边界条件：确定初始状态，即基本情况。

4. 计算顺序：确定计算的顺序，以便在需要时可以得到前面的计算结果。

5. 存储结果：使用数组或其他数据结构存储已计算的结果，以避免重复计算。

数组（Array）是一种基本的数据结构，用于存储一组相同类型的数据元素。数组的元素通常在内存中是连续存储的，因此可以通过索引快速访问每个元素。数组在计算机编程中非常常见，适用于许多不同的场景。数组是一种简单且高效的数据结构，广泛用于各种编程任务和算法实现。了解数组的基本特性和操作是学习算法和数据结构的重要基础。数组在很多高级数据结构（如哈希表、栈、队列和图）中也起着基础作用。

数组的基本特性

1. 固定大小：数组的大小在创建时确定，一旦设置后便不能改变（某些编程语言中有动态数组的概念，如 Python 的列表）。

2. 元素类型一致：数组中的所有元素通常是相同的数据类型，例如整数、浮点数或字符串。

3. 随机访问：由于数组的元素在内存中是连续存放的，可以通过索引快速访问任意位置的元素。访问时间复杂度是 O(1)。

4. 顺序存储：数组元素在内存中是顺序存储的，这使得它们在遍历时非常高效。

数组的基本操作

1. 创建数组：定义数组的类型和大小，并分配内存。

2. 访问元素：通过索引访问数组中某个元素。

3. 修改元素：通过索引修改特定位置的元素值。

4. 遍历数组：使用循环访问数组的所有元素。

5. 数组的排序和搜索：可以使用不同的算法对数组进行排序（如快速排序、归并排序等）和搜索（如线性搜索、二分搜索等）。

数组的应用

数组的应用非常广泛，包括但不限于：

• 数据存储：用于存储一系列相关的数据项，例如学生成绩、图像像素等。

• 数据处理：在科学计算、机器学习等领域，数组常用于数据的快速处理和分析。

• 动态编程：数组经常用于动态规划中的状态存储，帮助解决复杂的优化问题。

• 图像处理：在计算机视觉中，图像可以视为二维数组（像素矩阵）。

话不多说，直接上题：

2742.给墙壁刷油漆【困难】
题目：
给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。

示例 1：

输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。
示例 2：

输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。
提示：

1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10**6
1 <= time[i] <= 500
分析问题：
思路一：
        首先，我们需要理解问题的本质是在给定成本和时间的列表情况下，找到满足一定体积需求的最小花费。这个问题通过定义一个 dfs 函数来解决，函数中的参数 i 表示当前考虑的物品索引，j 表示剩余需要的体积。

        接下来，分析 dfs 函数的逻辑。当 j <= 0 时，表示剩余需要的体积已经满足要求，不需要再选择物品，所以返回 0 。当 i < 0 且 j > 0 时，表示没有物品可选但仍有剩余体积需求，这是不合法的情况，所以返回正无穷大 inf 。对于其他情况，有两种选择：一是选择当前物品，此时需要花费 cost[i] ，剩余需要的体积变为 j - time[i] - 1 ，然后递归调用 dfs(i - 1, j - time[i] - 1) ；二是不选择当前物品，直接递归调用 dfs(i - 1, j) 。函数返回这两种选择中的最小值。

        然后，要注意到使用了 @cache 装饰器进行记忆化搜索。这是为了避免重复计算相同的子问题，提高算法的效率。

        最后，在 paintWalls 方法中，通过获取 cost 列表的长度 n ，然后调用 dfs(n - 1, n) 来计算最小的花费。

思路二：
        首先，定义两个匿名函数 min 和 max ，分别用于求两个数中的最小值和最大值。

        然后，获取 cost 列表的长度 n ，并初始化一个列表 f 。 f[0] 设为 0 ， f[1] 到 f[n] 设为正无穷大 inf 。

        接下来，通过遍历 cost 和 time 列表的对应元素 c 和 t ，进行动态规划的计算。

        对于每个 c 和 t ，从 n 到 1 逆序遍历 f 列表。对于每个 j ，更新 f[j] 的值。更新的方式是取当前的 f[j] 和 f[max(j - t - 1, 0)] + c 中的最小值。 max(j - t - 1, 0) 表示在考虑当前时间 t 的情况下，能够完成的工作量对应的索引。通过这种方式，我们在每个位置 j 上，都找到了使用前 j 个物品能够达到的最小花费。

        最后，函数返回 f[n] ，即使用所有物品能够达到的最小花费。

代码实现：

思路一代码实现：

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        @cache  # 记忆化搜索
        def dfs(i: int, j: int) -> int:  # j 表示剩余需要的体积
            if j <= 0:  # 没有约束，后面什么也不用选了
                return 0
            if i < 0:  # 此时 j>0，但没有物品可选，不合法
                return inf
            return min(dfs(i - 1, j - time[i] - 1) + cost[i], dfs(i - 1, j))
        n = len(cost)
        return dfs(n - 1, n)

思路二代码实现：

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        # 定义一个匿名函数min，用于求两个数的最小值
        min = lambda a, b: b if b < a else a
        # 定义一个匿名函数max，用于求两个数的最大值
        max = lambda a, b: b if b > a else a
        n = len(cost)
        # 初始化一个列表f，f[0]为0，f[1]到f[n]为正无穷大
        f = [0] + [float('inf')] * n
        # 遍历cost和time列表的对应元素
        for c, t in zip(cost, time):
            # 从n到1逆序遍历f列表
            for j in range(n, 0, -1):
                # 更新f[j]的值，取当前f[j]和f[max(j - t - 1, 0)] + c的最小值
                f[j] = min(f[j], f[max(j - t - 1, 0)] + c)
        # 返回f[n]，即完成所有工作的最小花费
        return f[n]

总结：
 思路一代码详解：
定义了一个内部的 dfs 函数，该函数使用了记忆化搜索（通过 @cache 装饰器实现）。dfs 函数接受两个参数：i 表示当前考虑的物品索引，j 表示剩余需要的体积。
在 dfs 函数中，如果 j <= 0 ，表示剩余需要的体积已经满足要求，不需要再选择物品，返回 0 。
如果 i < 0 且 j > 0 ，表示没有物品可选但仍有剩余体积需求，这种情况是不合法的，返回 inf （表示正无穷大）。
对于其他情况，有两种选择：
选择当前物品（索引为 i ），那么需要花费 cost[i] ，并且剩余需要的体积变为 j - time[i] - 1 ，然后递归调用 dfs(i - 1, j - time[i] - 1) 。
不选择当前物品，直接递归调用 dfs(i - 1, j) 。
最后，函数返回这两种选择中的最小值。
在 paintWalls 方法中，首先获取 cost 列表的长度 n ，然后调用 dfs(n - 1, n) 来计算最小的花费。
        总的来说，这段代码的目的是通过递归的方式，在考虑每个物品的选择与否的情况下，计算出满足剩余体积需求的最小花费。记忆化搜索的使用可以避免重复计算，提高算法的效率。

考点：

动态规划：两段代码都运用了动态规划的思想来解决问题。通过定义合适的状态（如代码中的 f 数组）和状态转移方程（如更新 f[j] 的值），来逐步求解最优解。
函数定义与使用：代码中定义了匿名函数（如 min 和 max 函数）来简化比较和操作。
列表操作：涉及到列表的初始化、遍历（正序和逆序）以及元素的更新。
逻辑推理与问题分析：需要理解问题的要求，找出合适的解法，并将其转化为代码实现。
 

收获：

深入理解动态规划的概念和应用：通过实际解决这个问题，更加熟悉如何根据问题的特点定义状态和状态转移方程，从而有效地运用动态规划来求解最优解。
提高函数使用和定义的能力：学会了使用匿名函数来简洁地表达一些常见的操作，增强了代码的可读性和简洁性。
增强对列表数据结构的操作能力：包括列表的初始化、遍历和元素的修改，能够更加熟练地运用列表来解决实际问题。
培养逻辑思维和问题分析能力：在理解问题的基础上，能够将其转化为有效的算法和代码实现，提高了解决复杂问题的能力。
学会从不同的角度思考问题：两段代码虽然都解决了同一个问题，但实现方式略有不同，通过对比学习，可以拓宽解题思路，提高解决问题的灵活性。