Zeroize's Blog

2 - 网格图DP

发表于 2024-05-07 更新于 2024-05-13 分类于 cpp ，数据结构与算法， 5-动态规划 Waline：本文字数： 3.6k 阅读时长 ≈ 3 分钟

对于一些二维 DP（例如背包、最长公共子序列），如果把 DP 矩阵画出来，其实状态转移可以视作在网格图上的移动。所以在学习相对更抽象的二维 DP 之前，做一些形象的网格图 DP 会让后续的学习更轻松（比如 0-1 背包的空间优化写法为什么要倒序遍历）。

发表于 2024-05-07 分类于 cpp ，数据结构与算法， 3-搜索与图论，图论 Waline：本文字数： 2.9k 阅读时长 ≈ 2 分钟

快速入门图论！本文介绍图论中的“多源最短路”问题，以及解决它的Floyd算法，时间复杂度。

发表于 2024-05-07 Waline：本文字数： 66 阅读时长 ≈ 1 分钟

另外，对于 C++17，我们可以使用 <numeric> 头中的 std::gcd 与 std::lcm 来求最大公约数和最小公倍数。

发表于 2024-05-06 更新于 2024-05-07 分类于 cpp ，数据结构与算法， 3-搜索与图论，图论 Waline：本文字数： 7.1k 阅读时长 ≈ 6 分钟

快速入门图论！本文介绍图的”单源最短路“问题，并介绍解决这类问题的Dijkstra算法，BellmanFord算法和SPFA算法。

发表于 2024-05-05 更新于 2024-05-06 分类于 cpp ，数据结构与算法， 3-搜索与图论，图论 Waline：本文字数： 3.9k 阅读时长 ≈ 3 分钟

快速入门图论！本文介绍如何求图的出入度，然后介绍图的拓扑排序。