Category: 算法

2024
算法基础算法

微扰法 | 对频数进行计数排序

摘要: 对频数进行计数排序 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在排序问题中，如果元素的取值范围不大，可以通过计数的方式排序，突破基于比较的排序算法的 $\Omega(N\log N)$

算法字符串

字符串精确匹配的主流算法总结（含书籍推荐）

摘要: 字符串精确匹配方法汇总 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，此前我们讨论了字符串精确匹配的很多主流算法。 实际上字符串匹配算法是一个单独的大课题，这里推荐一本书 《Algo

算法字符串

暴力算法更实用：字符串匹配平均比较次数

摘要: 字符串匹配的暴力算法平均情况时间复杂度 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它

算法字符串

字符串精确匹配 | BM算法的变种-Horspool算法

摘要: BM算法的变种，Horspool算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字符串精确匹配的BM算法 中，我们介绍了字符串精确匹配的 BM 算法。在实际应用的经验中，BM 算

算法字符串

字符串精确匹配BM算法的变种：Sunday算法

摘要: BM算法的变种，Sunday算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在上一篇文章 字符串精确匹配的BM算法 中，我们介绍了字符串精确匹配的 BM 算法。在实际应用的经验中，BM

算法算法分析

一个算法分析的证明：概率方法证明上下界的范式

摘要: 通过概率方法讨论上下界的方式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个算法分析中的不起眼的问题，证明过程很简单，但是体现了一种证明的范式，这种范式跟香农信息论中

算法算法分析

斐波那契数的一个渐近下界 | Dijkstra算法+斐波那契堆的基础

摘要: 斐波那契堆时间复杂度推导的基础 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，关注算法的学生和工程师最近可能刷到了一篇关于 Dijkstra 算法的文章。我是在量子位上首先刷到的，后

算法leetcode

【线性枚举】力扣910-最小差值2

摘要: Ad-Hoc 问题，算法就是个线性枚举，但难在分析清楚问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个稍微有点统计学背景的题，涉及到描述性统计中的极差的概念。给定

算法leetcode

【贪心】力扣3191-使二进制数组全部等于1的最少操作次数I

摘要: 一道平平无奇的贪心 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个在一个二进制串上翻转的问题，经过分析后可以找到贪心算法。 题目 3191. 使二进制数组全部等于 1

算法leetcode

【值域二分+找规律】力扣3200-三角形的最大高度

摘要: 值域二分+找规律 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文看一个简单题，算法的框架是值域二分，二分的判定阶段不涉及算法，但是需要找规律，这里需要条理比较清晰，不然容易卡柱。 题目

算法算法分析

动态数组的扩容为什么经常是两倍扩容

摘要: 动态扩容数组的分析 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 我们在编程中经常会用到数组。初始化一个数组时需要分配一块连续的内存空间，那么这就需要在分配的时候知道数组的长度，但业务场景中

算法算法分析

摊销分析：基于统计力学的势函数法

摘要: 摊销分析的势函数法初探 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 摊销分析的方法有很多种，最直接的方法是直接计算完成一系列操作的运行时间的上界，这也是前面的文章 可清空表的摊销分析 中使

算法算法分析

摊销分析：基于财务模型的记账法

摘要: 记账法的摊销分析 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 可清空表的摊销分析 中，我们提到在数据结构中，不同操作的时间复杂度有差异，以及一串操作序列中不同操作会互相影响的情况，

算法算法分析

可清空表的摊销分析

摘要: 摊销分析的例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，前面几篇文章我们讨论了一些数据结构。根据实际需求设计的一个数据结构，往往支持很多操作。当我们谈这个数据结构的效率怎么样的

算法leetcode

Ad-Hoc问题：乘积最大的子序列

摘要: 整数全选，负数选最小的偶数个，若除零外只有一个负数则答案为零 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们看一个常规的算法题。这也是一个 Ad-hoc 题，把问题分析清楚即

算法动态规划

最长好子序列2：动态规划难题的完整思考过程

摘要: 避免枚举所有可能的决策 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文是上一篇文章 最长好子序列1：猜想出最优子结构 的延续，题目完全相同，只是数据量级增加了，原有的算法必须优化

算法动态规划

最长好子序列1：猜想出最优子结构

摘要: 猜出最优子结构并不容易 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文看一个动态规划的问题。依然是需要在草稿纸上推导小数据的情况时，猜出最优子结构。这是第一步难点，下一步是动态规

算法疑难杂症

Ad-Hoc问题：分析特定问题的独有性质

摘要: 分析问题的性质 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在通信网络中，有一类称为 Ad-hoc 网络。ad-hoc网络是一种特殊的网络模式，它允许一组设备（如计算机、手机等）通过无线方

算法基础算法

范围缩放法证明贪心的正确性

摘要: 范围缩放法例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文看一个比较简单的贪心算法的问题，思路和算法很好想。这个题值得分享的亮点是这是使用范围缩放法证明贪心正确性的例子。 范围缩放法

算法leetcode

用哈希表维护次小值信息

摘要: 哈希表维护的信息怎样设计 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个哈希表的灵活应用问题，主要难点在于哈希表的键和值维护什么信息，怎样设计。 题目 3143. 正

算法疑难杂症

思维复杂代码简单与思维简单代码复杂

摘要: 将问题转化为 TopK 问题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个思维量比较大的题，一种直接的思路还是非常好想的，但是过程比较繁琐，有一些边界情况需要讨论

算法搜索

将问题转化为枚举全排列的问题

摘要: 问题转化：将问题转化为枚举全排列 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个看似简单的题，但还是有一个小难点就是能够想到这是一个枚举全排列的问题。这需要进行一些问

算法图算法

通过建图将问题转化为图上的搜索问题

摘要: 难点在于正确建图 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个通过建图将问题转化为图上的搜索问题，难点在于正确建图。 题目 2101. 引爆最多的炸弹 给你一个炸

算法动态规划

动态规划的难点，找到最优子结构：排序后再尝试各种额外信息

摘要: 子序列的枚举与顺序无关 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个动态规划的困哪题，主要难点还是如何发现最优子结构。 本题是在经过排序之后，进一步尝试各种额外信息

算法疑难杂症

算法不难，难在分析问题：双指针推进过程枚举所有答案

摘要: 经过分析，发现双指针可以解决问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们看一个困难的计数问题，也是出在某次周赛的最后一题。 仅从算法上看，本题只涉及一个双指针，谈不上

算法基础算法

一维散点到定点的距离之和

摘要: 前缀和的应用：推导后得到含区间和的表达式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 给定 n 个点，然后问这 n 个给定点到某个点的距离之和。要算出这个值，最直接的做法是先计算 n 个给

算法动态规划

难以发现的最优子结构：归纳与猜想 | 合情推理 | 问题转化

摘要: 分析问题的过程猜出最优子结构 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们解决过大量的动态规划问题，并且也了解了一些理论，对常见问题也形成了套路。 但是有些问题还是需要一些灵光一闪

算法搜索

回溯法的搜索树规模的上界估计

摘要: 暴力算法怎样实现评估可不可行 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们系统了解过回溯法，并解决了很多问题，参考文章 回溯法的思想、设计与分析。回溯法其实就是一种暴力方法，因此在

算法动态规划

减治型区间DP，一个例子

摘要: 一个减治型区间 DP 的例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于区间动态规划来说，阶段是区间的长度，附加信息是区间的左右端点，其状态表示一般为 $dp[i][j]$ 表示区间

算法基础算法

问题的拆解、抽象与转化

摘要: 将新问题转化为已经解决过的老问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 当我们拿到一个新问题时，一个重要的思想是将其转化为已经解决过的老问题。具体的转化方法需要结合具体问题，比较有技

算法动态规划

DP优化思路：用变量记录已推导状态的最值，供后续状态的推导使用

摘要: 一个动态规划优化的直接思路 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在某些动态规划的问题中，状态转移方程类似于以下形式： dp[j] = f(\max\limits_{0\leq i

算法基础算法

反悔贪心：每天可以买进一股/卖出一股/不操作的股票问题

摘要: 反悔贪心的一种实现：通过精巧的公式设计，跟着贪心策略可以自动执行反悔 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 反悔贪心与反悔堆的思想，带截止时间的任务选择问题 中我们介绍了反悔

算法基础算法

偷k个房间的打家劫舍问题：双向链表维护的反悔贪心策略

摘要: 贪心过程自动反悔的精巧设计 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续看一个反悔贪心算法的精巧设计。本题首先比较容易想到一种贪心思路，但有些问题，需要反悔机制进行纠正

算法基础算法

反悔贪心与反悔堆的思想，带截止时间的任务选择问题

摘要: 反悔贪心的思想，带截止时间的任务选择问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于具有最优子结构的问题，如果整体最优解可通过一系列局部最优解的选择达到，并且每次选择可以依赖以前作出

算法数学算法

推公式解决问题

摘要: 推公式的题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 有一类问题，其求解的过程主要依赖于一些公式推导，只要公式推出来，在实现的时候只需要按公式来就行，不涉及什么算法或数据结构。 如果推

算法图算法

无向图的最小环问题

摘要: 无线图最小环问题：Floyd变形、Dijkstra变形 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一下无向图中求长度最短的环的问题。 如果无向图是带权的，那么算法是在 Floy

算法基础算法

一类带约束条件的最优选择问题

摘要: 堆贪心解决带约束条件的最优选择问题，放松约束条件使得候选对象越来越多 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在业务场景中，我们经常遇到这样一类优化问题。有一个对象池，其中的每个对象有

算法基础算法

带约束条件的TopK选择问题，反悔贪心的思想

摘要: 堆贪心解决带约束条件的 TopK 问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings TopK 问题是算法中的一大类问题，很多问题可以抽象为 TopK 问题，然后用 TopK 问题的算法解决

算法字符串

处理重复叠加串上的匹配问题：滚动哈希法

摘要: 滚动哈希例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字符串哈希 中，我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决，比如最长重复子串（力

算法字符串

多次查询两个子串是否相等：前缀哈希法

摘要: 可以用字符串哈希解决的经典问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 字符串哈希 中，我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决，比

算法字符串

字符串精确匹配的BM算法

摘要: BM算法原理与代码模板 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它是一种预处理+响

算法搜索

回溯法最经典问题-数独

摘要: 数独的状态空间树与回溯法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 回溯法的思想、设计与分析 中，我们系统了解了回溯法的思想。 我们知道要用回溯法解决问题，首先需要明确问题的解空

算法字符串

字符串的循环同构与最小表示法

摘要: 循环同构字符串中哪个字典序最小 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 问题背景给定一个字符串 s，如果不断把最后一个字符放在开头，最终会得到 $n$ 个字符串，称这 $n$ 个字符串

算法动态规划

两枚鸡蛋的鸡蛋掉落：单峰性、决策单调性、差分方程

摘要: 单峰性、二分优化 DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本题是基于各种单调性设计算法的经典例子，也是基于目标函数的单峰性、决策单调性优化 DP 的经典例子。从算法的大框架看，有

算法动态规划

决策单调性的简单情况：决策候选集随状态推导递增而目标函数不变

摘要: 决策单调性的简单情况 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 决策候选集与最优决策考虑以下状态转移方程： dp[i] = \min\limits_{1\leq j 在推导状态 $dp

算法动态规划

单峰性与二分优化DP：N个鸡蛋掉落问题

摘要: 单峰性、二分优化 DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 我们知道如果一个序列是呈现出单调性的时候，经常设计基于二分的算法。对于动态规划的状态转移方程中，最优决策候选集合有时会呈

算法动态规划

求解差分方程/函数方程优化DP：N个鸡蛋掉落问题

摘要: 可以直接作为差分方程/函数方程求解的状态转移方程 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于某些简单的状态转移方程，可以直接作为差分方程/函数方程求解出来。求通项公式很可能会比直接推

算法动态规划

使得乘积最大的整数分拆：基于数学性质对决策空间剪枝

摘要: 动态规划解决数列第 n 项问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings \max\limits_{\substack{2 \leq k \leq x \\ \sum_{i=1}^{k

算法动态规划

计数DP：基于初等计数原理与容斥原理设计状态表示

摘要: 带限制的排列数目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个比较困难的计数问题。统计带有某种限制的排列数目，给定的参数有 $n, l, d$ 三个，其中 $n$ 是物品种类

算法动态规划

在DP状态转移的DAG上BFS：从动态规划的角度理解无权图最短路径

摘要: 在 DP 状态转移图上 BFS 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在组合数学中，在很多与数列 $\{a_{n}\}$ 相关的问题：给定初始值 $a_{0}, a_{1},\cd