Home

汇文150周年

摘要: 2021 年 10 月 06 日,高中学校北京汇文中学 150 周年校友返校日。 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 校门 教学楼门 生物老师 英语老师 语文老师

【leetbook】动态规划精讲-目录

摘要: 动态规划系列的 4 本 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 动态规划精讲1 01 概述 02 动态规划简介 动态规划的背景 解决动态规划问

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

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

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

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

可清空表的摊销分析

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

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 在上一篇文章 数据直觉:任意数据集都很难有偏离均值多倍标准差的数据 中,我们简要介绍了数据集

数据直觉:任意数据集都很难有偏离均值多倍标准差的数据

摘要: 对任意数据集,很难有偏离均值多倍标准差的数据 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 新拿到一份业务数据,在分析这份数据的时候,我们往往从均值和标准差入手。本文我们推导均值和标准差的两

博弈论:二元函数的鞍点定理

摘要: 二元函数的鞍点 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 minimax算法初探以及若干例子 中,我们介绍了博弈算法中最重要的 minimax 算法,其背后是二人有限零和博

夹逼定理加放缩法,将和式放缩为最值

摘要: 夹逼定理+放缩法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 由p范数诱导的距离,当p趋于无穷时为切比雪夫距离 中,我们主要证明了 p 范数诱导的距离当 $p \rightarro

由p范数诱导的距离,当p趋于无穷时为切比雪夫距离

摘要: 切比雪夫距离与闵可夫斯基距离的关系 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前我们解决过很多几何问题。这些几何问题都是在欧式空间的框架下的。在文章 几何题汇总 中我们总结了几何问题相

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

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

用哈希表维护次小值信息

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

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

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

简明微积分:从零推导理想流体的欧拉方程

摘要: 推导无粘滞流体力学的欧拉方程,参考《简明微积分》 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 《简明微积分》关于微积分和数学分析的好书有很多,本文介绍一本内容安排上比较独特的书,龚昇的《简

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

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

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

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

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

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

一个有概率背景的抽象不等式,积分中值定理的应用

摘要: 积分中值定理主线梳理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一个抽象不等式。该不等式描述了一类随机变量 $X$ 的期望的一个下界:如果 $X$ 的取值范围为 $[a, b

概率方法的威力:由数学期望的性质推导出不等式

摘要: 概率方法在不等式证明中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,今天我们继续看一个概率方法在证明不等式时的威力,整体上的方法与 一个微分不等式,概率方法的威力 中类似,只

一个微分不等式,概率方法的威力

摘要: 概率方法证明微分不等式一例 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 我们大学以及考研的时候都学过微分中值定理。书上给出的形式是 $f(b) - f(a) = f’(\xi)(b - a

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

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

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

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

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

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

Schweitzer不等式,概率方法的威力

摘要: 概率方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 概率方法证明不等式:构造随机变量,将不等式中的项解释为事件的概率 中,我们介绍了证明不等式的概率方法,在文章 Weier

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

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

Weierstrass不等式,概率方法的威力

摘要: 概率方法在证明不等式中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 对于具有最优子结构的问题,如果整体最优解可通过一系列局部最优解的选择达到,并且每次选择可以依赖以前作出

系数均为1的线性不定方程解的个数:母函数与容斥原理

摘要: 母函数+容斥原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 设 $a_{1}, a_{2}, \cdots, a_{n}$ 为非零整数,$b$ 为整数,关于未知数 $x_{1}, x_{

原公司注销,将公众号迁移至新公司

摘要: 公众号迁移流程 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的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 在文章 字符串哈希 中,我们学习了字符串哈希的原理和代码模板。 一些字符串中的经典问题用字符串哈希都可以解决,比

完全数,因子之和函数

摘要: 完全数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们介绍一下最早由古希腊人提出的完全数,也称完美数。对于一个正整数 $n$,如果除它自身以外所有的正因子之和等于该正整数 $n$ 自

回溯法最经典问题-数独

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

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

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

图的维纳指数:反映图的扩散性的拓扑不变量

摘要: 图的维纳指数,反映图的扩散性的拓扑不变量,图算法计算 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 图的维纳指数最初引入是在化学领域,用于描述分子结构,这是一个图上的拓扑不变量,1947 年

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

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

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

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