当前位置：首页 > news >正文

DP动态规划（下）

news 来源：原创 2024/9/29 15:33:03

文章目录

如何在动态规划中有效地使用`std::unordered_map`?
以下是使用`std::unordered_map`进行动态规划的一些关键点：
选择合适的键：
考虑哈希冲突：
优化哈希函数：

下面是一个使用`std::unordered_map`解决斐波那契数列问题的例子：

-迷你结-
如何处理动态规划中的边界条件?
明确问题的起始状态：
定义状态和状态转移方程：
设置基础情况：
防止数组越界：
特殊状态处理：
文档化边界条件：

-迷你结-
C++中的动态规划解决方案是否适用于其他编程语言？
定义状态：
初始化：
状态转移方程：
遍历顺序：
记忆化：

迷你结
如何优化动态规划的内存使用以避免空间复杂度过高？
空间优化技术：
滚动数组/一维数组：
空间换时间：
原地修改：
递归优化：
迭代而非递归：
压缩状态表示：
使用哈希表代替数组：
滑动窗口技术：

迷你结

大结
-结-
-DP动态规划-

文前声明：
由于Java我并不熟悉，大部分资料来源于网络，不正确的地方请在评论区留言告诉我！
DP这一块会比较难，篇幅较长，请耐心看完
喜欢的话请按小红心，您的支持是我最大的动力！

动态规划（Dynamic
Programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。这种方法通常用来解决具有重叠子问题和最优子结构特性的问题，以减少重复计算并找到全局最优解。

————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：上一篇/这一篇

如何在动态规划中有效地使用`std::unordered_map`?

在动态规划问题中，std::unordered_map可以被用作备忘录（memoization）技术的一部分，以存储中间计算结果并避免重复计算。相比于std::map，std::unordered_map提供了平均时间复杂度为 $O (1)$ 的查找、插入和删除操作，这在动态规划中尤其有用，因为通常需要频繁地查询和更新状态。

以下是使用`std::unordered_map`进行动态规划的一些关键点：

选择合适的键：

• 键应该能唯一标识一个状态。
• 如果状态由多个变量决定，可以将它们组合成一个复合键，例如使用元组（在C++17及以上版本中使用std::tuple或std::pair）或者将变量编码为一个长整型（例如，使用位运算）。
• 初始化
std::unordered_map：

使用默认构造函数创建std::unordered_map实例。>>
可以指定哈希函数和键的比较器（如果键类型不是基本类型，且标准哈希和比较不适用的话）。
使用find或[]操作符访问状态：

使用find方法检查键是否存在，如果不存在则返回end()迭代器，可以结合insert来插入新值。
使用[]操作符可以直接获取或插入键值对，但要注意它会自动插入键，即使键之前不存在。

考虑哈希冲突：

虽然std::unordered_map的平均查找时间是 $O (1)$ ，但在最坏的情况下，如果哈希函数分配不当，性能可能会退化至 $O (n)$ 。

优化哈希函数：

如果键的类型允许，编写一个更高效的自定义哈希函数可以提高性能。
对于复合键，确保所有组成部分都被考虑在内，并且哈希函数均匀分布以减少冲突。

下面是一个使用`std::unordered_map`解决斐波那契数列问题的例子：

#include <unordered_map>long long fib(int n, std::unordered_map<int, long long>& memo) {if (n <= 1)return n;// Check if value is already computedauto it = memo.find(n);if (it != memo.end())return it->second;// Compute and store the valuelong long result = fib(n - 1, memo) + fib(n - 2, memo);memo[n] = result;return result;
}int main() {std::unordered_map<int, long long> memo;int n = 50; // Calculate the 50th Fibonacci numberstd::cout << "Fibonacci(" << n << ") = " << fib(n, memo) << std::endl;return 0;
}

-迷你结-

在这个例子中，memo是一个std::unordered_map，用于存储已计算的斐波那契数。每次计算新的斐波那契数时，都会先检查memo中是否已有结果，如果没有，则计算后将其存入memo。这样就避免了重复计算相同的子问题，显著提高了效率.

如何处理动态规划中的边界条件?

处理动态规划问题时，正确设定边界条件是至关重要的，因为它们直接影响到递推关系式的建立及最终解的准确性。以下是一些处理边界条件的基本步骤和建议：

明确问题的起始状态：

首先，识别动态规划问题的初始状态。这是递推过程开始的地方，通常对应着问题规模最小的情况。例如，在计算斐波那契数列时，F(0)=0和F(1)=1󠁪就是边界条件。

定义状态和状态转移方程：

确定状态变量及其含义，然后根据问题逻辑构建状态转移方程。边界条件通常用于直接给出或推导出最基本状态的值。

设置基础情况：

明确哪些是不需要进一步分解的最基本情形，并直接给出它们的解。这些基础情况通常是递归终止条件，例如，最短路径问题中起点到自身的距离为0。

防止数组越界：

在实现动态规划时，确保数组或数据结构的索引不会超出边界。根据状态定义合理初始化数组大小，并在循环中正确控制索引。

特殊状态处理：

对于某些特定输入或特殊情况，可能需要额外的边界条件处理。例如，在某些序列问题中，空序列或单元素序列可能需要特别考虑。
验证边界条件的合理性：
在实现后，通过测试用例特别是边界案例来验证边界条件的正确性，确保没有遗漏或错误。

文档化边界条件：

在代码中清晰注释边界条件，有助于他人理解和维护代码。
举例说明，在背包问题中，边界条件可能包括背包容量为0或没有物品可选时，最大价值为0；而在最短路径问题中，从源节点到自身的距离为0，这些都是直接给出解的边界情况。

-迷你结-

综上所述，边界条件的设定需要根据问题的具体情况仔细考虑，确保递推过程能够正确启动，并最终导向问题的解答。

C++中的动态规划解决方案是否适用于其他编程语言？

动态规划的核心思想和解决方案策略是跨语言的，这意味着在C++中实现的动态规划解决方案的基本原理和算法逻辑同样适用于其他编程语言，如Java、Python、JavaScript等。动态规划主要依赖于以下几个关键点：

定义状态：

明确表示问题状态的方式，这通常通过变量或数据结构来实现。

初始化：

确定初始状态的值，通常是问题的最简单形式或基本情况。

状态转移方程：

表达状态之间如何通过计算相互转换的公式或逻辑。

遍历顺序：

决定如何遍历状态空间，通常采用循环或递归来实现。

记忆化：

使用数据结构（如数组、哈希表等）来存储中间结果，避免重复计算。
不同编程语言在实现这些步骤时的语法和库支持会有所不同，但算法的核心逻辑保持一致。例如，C++中可能使用数组或std::vector来存储状态，而在Python中可能倾向于使用列表（list）或字典（dict）。Java开发者可能使用数组、ArrayList或HashMap等。
下面是相同问题（最长公共子序列，LCS）在Python中的实现示例，以展示动态规划解决方案的跨语言适应性：

def longest_common_subsequence(text1, text2):m, n = len(text1), len(text2)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):for j in range(1, n + 1):if text1[i - 1] == text2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]text1 = "ABCBDAB"
text2 = "BDCAB"
print("Longest Common Subsequence length:", longest_common_subsequence(text1, text2))

迷你结

这段Python代码实现了与上述C++示例相同的功能，展示了动态规划算法在不同编程环境中的通用性和适应性。

如何优化动态规划的内存使用以避免空间复杂度过高？

优化动态规划的内存使用，尤其是减少空间复杂度，是提高算法效率的一个重要方面。以下是一些常用的技术：

空间优化技术：

滚动数组/一维数组：

在许多情况下，动态规划表格中只有一行（或一列）是活跃的，即当前行的计算仅依赖于前一行的结果。因此，可以使用一个一维数组替代二维数组，每次计算完一行后覆盖旧的数据。以最长公共子序列为例，原本的二维dp数组可以降为一维，每次更新时只保留当前行和上一行的信息。

空间换时间：

虽然通常我们寻求减少空间使用，但在某些情况下，预计算并存储更多的数据可以减少后续计算，从而提升整体效率。这需要权衡空间和时间复杂度。

原地修改：

对于一些问题，可以考虑直接在输入数据上进行操作（如果允许），或者使用输入数据的一部分作为临时存储，减少额外内存的分配。

递归优化：

如果使用递归实现动态规划，可以通过记忆化递归（自顶向下，带缓存）减少重复计算，同时注意及时清理不再需要的缓存项，以避免内存泄露。

迭代而非递归：

递归可能导致大量的调用栈，消耗内存。改用迭代方法（自底向上）通常可以减少内存使用。

压缩状态表示：

对于某些问题，状态可以用更紧凑的形式表示。例如，在某些状态转移中，只有有限的状态值是有效的，可以使用位运算来存储和操作状态，从而大幅减少空间需求。

使用哈希表代替数组：

当状态数量巨大但实际使用的状态远少于理论可能的状态时，可以使用哈希表（如unordered_map󠁪或dict）来存储必要的状态，从而减少内存占用。

滑动窗口技术：

在处理序列问题时，如果状态只与最近的几个元素有关，可以使用滑动窗口来维持这些元素，而不是存储整个序列的状态。

迷你结

通过应用以上技术，可以在保持算法正确性的前提下，有效降低动态规划问题的空间复杂度，提升算法的实际运行效率。

大结

动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学以及经济学等领域广泛应用的求解最优化问题的方法。它的核心思想是通过把原问题分解为相对简单的子问题，并且存储子问题的解，从而避免了重复计算，高效地解决具有重叠子问题和最优子结构的问题。

一个完整的动态规划问题分析通常包括以下几个步骤：

确定问题具有最优子结构
首先，需要确认问题是否具有最优子结构，即原问题的最优解可以通过子问题的最优解组合得出。这是动态规划适用的前提条件。
定义状态和状态转移方程

定义状态：明确问题中需要做出决策的变量及其可能取值。例如，在背包问题中，状态可能是“前i个物品放入容量为j的背包中的最大价值”。
状态转移方程：表达如何从已解决的子问题的解推导出更大问题的解。这一步是动态规划的核心，它描述了状态之间的依赖关系。例如，背包问题的状态转移方程可能是
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
，表示考虑第i个物品时，要么不选该物品，要么选择该物品并更新背包剩余容量下的最大价值。

边界条件和初始化
确定动态规划表的边界条件，即最小子问题的解。例如，在上述背包问题中，初始时dp数组的值可能根据背包容量和物品重量设定，如
dp[0][j] = 0
表示没有物品时背包的价值为0，
dp[i][0] = 0
表示背包容量为0时无法放置任何物品。
选择合适的计算顺序
决定是采用自顶向下（递归+记忆化搜索）还是自底向上（迭代）的方式来填充动态规划表。自顶向下方法从较大的问题开始，逐步分解；自底向上则从最小的子问题开始，逐步构建更大的解。
构建解决方案
根据动态规划表的信息，逆向构造出问题的最终解。这一步可能需要回溯记录哪些子问题的选择导致了最终的最优解。
实例分析：斐波那契数列
以斐波那契数列为例，动态规划分析如下：