Category: 算法

沃利斯积分的分段渐近估阶:拉普拉斯方法的思想启蒙

摘要: 分段渐近估阶的例子,与实践中的注意事项 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 冒泡排序平均需要跑多少趟:拉马努金Q函数初探 和 插入多少次发生哈希冲突:拉马努金Q分布与二元渐

插入多少次发生哈希冲突:拉马努金Q分布与二元渐近分析

摘要: 拉马努金 Q 函数及其在算法分析中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们继续讨论算法分析中的问题。 在哈希算法的分析中,哈希冲突是最受关注的问题。考虑有一个长

冒泡排序平均需要跑多少趟:拉马努金Q函数初探

摘要: 拉马努金Q函数在算法分析中的应用,初步体验 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们继续来讨论算法分析中的问题。 很多数组上的算法都与 $1 \sim n$ 的排列有关

n节点的无序标号树有多少种:拉格朗日反演的应用

摘要: 拉格朗日反演的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们继续来讨论算法分析的问题。 对于图论中的很多算法,其时间复杂度的分析经常需要基于 n 节点的无序标号树共有多

二叉树的计数:直接方法与间接方法

摘要: 通过二叉树计数的基础问题,了解生成函数计数的直接方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在对与二叉树相关的算法进行算法分析时,一个非常基本的问题是:给定一些条件,问满足这些条件的

生成函数的性质速查

摘要: 生成函数的性质 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 生成函数即母函数,有时也叫形式幂级数。是组合数学中的一个重要理论和工具。 生成函数的一个重要线索来自于 18

算法分析中的欧拉方程:基于三数中值法的快速排序

摘要: 三数中值法的快速排序,欧拉方程的求解 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在大学高等数学或考研高等数学中,我们学过几类容易求解的常微分方程的解法,特别地对于常系数

渐近估阶的威力:欧拉-麦克劳林公式的应用

摘要: 用欧拉-麦克劳林公式对调和级数估阶 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来讨论一下算法分析中的问题。 由于递归和迭代是最常见的两种程序结构。因此时间复杂度 $T(n

先找规律后推公式,自然数幂和公式

摘要: 找规律,推公式 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们看一个值域二分的问题。假设有一个 $f(x)$,我们想知道使得 $f(x) \geq M$ 成

二维差分:用邮票贴满网格图

摘要: 二维差分 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在一维数组上,前缀和与差分是一种常见的处理区间求和问题的算法,参考文章 【模板】前缀和与差分。 如果二维的矩阵上有类似的与求和有关的问

极值栈与极值队列

摘要: 极值栈,极值队列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 极值栈是指除了维护栈的基本功能之外,还需要随时查询栈中的最值。它的设计思想是用两个栈来维护,其中一个栈维护数据的插入删除,另一

双单调栈:两侧距离第二近的更大元素

摘要: 双单调栈 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 单调栈是一种在数组上摊销 $O(1)$ 地解决以下问题的数据结构:对于 $nums[i]$,求两侧距离最近的大于 $nums[i]$

leetcode第375场周赛

摘要: 本文是 leetcode 第 375 周赛的记录。主要涉及的算法包括惰性更新、模下快速幂、组合数学、区间合并 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 总览本周进行了 leetcode

树的最大权独立集:树形DP

摘要: 树形DP解决树上最大权独立集问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于没有自环的图 $D$,$S$ 为 $V(D)$ 的子集,若 $S$ 中任意两点均不相邻,则称 $S$ 为

力扣1670-设计前中后队列

摘要: 基于链表的设计 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个基础数据结构的设计问题。难点在于增删的时候如何维护指向链表中间节点的指针。细节处理非常繁琐,不容易过。 题目请你设计一

给定树的遍历序-重建一棵可能的树

摘要: BFS 序和 DFS 序结合的经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 遍历序的概念与性质 中,我们了解了树的各种遍历序。本文我们看一个直接的问题,如何从树的遍历序,构

中心扩散法

摘要: 枚举中点,看两边能扩散多长 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过最长回文子串问题,看一下数组上关于子数组的问题的两种不同方向的思考方式,一种是首先确定子数组的两端 l, r

在数据结构中维护前缀和:区间(矩形/路径)和等于(大于)目标值

摘要: 区间和等于目标值的各种变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】前缀和与差分 中我们了解了一维和二维前缀和的算法原理和代码模板。在实际问题中我们经常要将前缀和维

RANSAC算法:应对大比例异常值

摘要: RANSAC 算法思想 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings RANSAC 算法是一种随机算法,它用迭代的方式从一组含有离群点的一组观测数据中估计数学模型的参数。本文首先简要介绍这种

设计内存文件系统:在Trie中用TreeMap维护子节点

摘要: TreeMap 维护子节点的 Trie 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 Trie 中,一般用数组或哈希表维护子节点,本文我们看一个用TreeMap维护子节点的例子。 题

Trie单串多模式匹配

摘要: 单纯多模式匹配 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个 Trie 可以完美解决的字符串匹配需求,单串多模式匹配,且模式中的字符没有限制,也就是单串中的每个字符都有可能是

打家劫舍:不相邻子序列最大和问题

摘要: 不相邻的子序列最大 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 最大子数组和的三种解法 中我们解决了最大组数组和的问题,以该问题为基础问题有很多变种,在文章 目标带绝对值的处理:最

力扣2216-美化数组的最少删除数

摘要: 定式化的动态规划、技巧性的贪心 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文的题目有动态规划和谈心两种解法。其中动态规划的思路比较定式化,更好想一些。贪心需要一些灵感和技巧,并且涉

调整状态定义的方向:简化实现过程

摘要: 状态定义的方向的影响 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 状态计算的方向:从已知状态计算当前状态;从当前状态更新后续状态 中,我们知道当阶段划分与状态定义完成后,还可以转换

二维偏序问题:扫描线+树状数组

摘要: 一个维度用扫描线(排序)保证有序;一个维度用树状数组保证有序;维护权值的最值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 二维偏序问题形式化定义如果形式化地定义,二维偏序问题的描述如下。

阶段不足以表示可推导的状态:附加信息作为状态维度

摘要: 找到阶段划分后,有时发现需要增加附加信息才能得到可以推导的状态表示 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于一个动态规划的问题。最重要的是找到状态表示和阶段划分,其中阶段划分相对

理解高维状态空间线性DP:已处理部分在状态空间中的轮廓

摘要: 状态计算的方向 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过照相排列问题 (k 个串上的线性 DP),来理解一个动态规划中的一个抽象的概念:已处理部分在高维状态空间中的轮廓。可

状态计算的方向:从已知状态计算当前状态;从当前状态更新后续状态

摘要: 状态计算的方向的影响 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划中,当状态表示和阶段划分给定,状态转移方程可以有两个方向的写法可以选,分别对应不同的考虑方式,一个是考虑从先前阶

带权DAG上的最长路径:拓扑序DP

摘要: 拓扑序DP解决带权DAG上的最长路径问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 DAG上的DP (拓扑序DP):无权 DAG 的最长路径 中我们介绍了 DAG 上的拓扑序 D

不同路径系列问题:计数DP,以初等计数原理划分阶段和子问题

摘要: 状态的各决策间满足加法原理,决策划分的子状态间满足乘法原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 动态规划中的计数类问题,主要强调“不重不漏”。因此如果用动态规划解决的话,子结构的划

状态=阶段+附加信息;排除高维状态空间的冗余维度

摘要: 状态=阶段+附加信息,其中有冗余信息的优化方法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 高维空间动态规划仅把 DP 的阶段要素放到 DP 状态中有时不足以找到最优子结构,也就是不足

决策候选集随阶段的推导递增的情况,LCIS问题

摘要: 决策集合的维护 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最长上升子序列(LIS)和最长公共子序列(LCS)是单串和双串场景下的动态规划的状态设计思路。 将这两个合起来,形成最长

最优决策序列个数

摘要: 动态规划解决优化问题,求最优决策方案数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划的问题中,有时会遇到求某个具体的最优决策序列的问题,在 求具体的最优决策序列 中已经解决。 本

数字三角形与数字矩形:两类最经典的棋盘DP状态设计

摘要: 数字三角形问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过数字三角形和数字矩形这两个简单问题来看一下棋盘 DP 的两类基本设计思路。 在棋盘 DP 的问题中,比较常见的有两种

求具体的最优决策序列

摘要: 动态规划解决优化问题,求具体决策序列 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在动态规划解决的优化问题中,有时需要给出具体的最优方案。最直接的做法是额外使用一些与 DP 状态大小相同的

二维的滑动窗口最大值

摘要: 滑动矩形窗口最大值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 滑动窗口最大值问题是单调队列的最典型使用场景,单调队列也是定长滑动窗口问题的最优解法,时间复杂度为 $O(N)$,参考文章

离线分治:基于时间 (CDQ分治)

摘要: 基于时间的离线分治,逆序对个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 很多数据结构的问题可以抽象为“维护一系列数据,并对一系列操作一次做出响应”,这些操作可以分为两种: 查询型操作

树状数组优化DP

摘要: 权值树状数组优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 最长上升子序列LIS 我们通过动态规划解决了最长上升子序列问题,其状态转移方程如下: dp[i] = 1 + \m

归并树:区间大于x的元素个数

摘要: 归并树,区间大于 x 的元素个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 315. 计算右侧小于当前元素的个数 出发,引出一个维护区间大于 x 的元素个数的数据结构:归并树

划分树:区间第k大

摘要: 划分树,区间第 k 大数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 力扣315-索引数组,归并树 出发,引出一个维护区间第 k 大数的数据结构:划分树。 对于区间 $[i,

分块查找表:区间修改,区间最值查询

摘要: 分块查找表,原理与实现,解决带修改的区间最值查询问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分块查找表的主要思路是对于数据数组 nums[0..n-1], 共 n 个元素,每 $\s

Range模块:维护区间的增删改查

摘要: 基于平衡树的Range模块,维护区间的增删改查 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过力扣 715 来看一下可以动态维护区间的增删改查的组件的功能与实现,本题的代码可以作

问题规约的艺术:无向基环树的直径

摘要: 基环树的概念与例子 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于无向图,N 个点的树有 N - 1 条边,在树上任意加一条边,会形成一个环,除了环之外,其余部分由若干子树构成。 这种

【搜索难题】力扣2258-逃离火灾

摘要: 搜索题,思路简单,细节复杂 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个搜索题。思路比较清晰,不过细节很复杂。需要针对人和火搜索两次。第二次既可以 BFS 也可以

二维转一维

摘要: 基于一维问题的解法,解决二维问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 一维数组上有一些常见的问题,应用了正确的算法后可以很好地解决。这些问题经常在二维矩阵上也有类似的问题。比如一维

前驱后继与线索二叉树

摘要: 线索树 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对树进行遍历的过程中,会产生一个遍历序,参考文章 遍历序的基本概念与性质。基于这个遍历序,每个节点都有一个前驱节点与后继节点。 在实际问

n皇后-同一问题构造不同的状态空间树

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

回溯法三种常见的状态空间树:子集树、排列树、满m叉树

摘要: 三种常见的状态空间树 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 回溯法在文章 回溯法的思想、设计与分析 中,我们系统地了解了回溯法的思想。 回溯法是一种在解空间中搜索可行解或最优解的方法

回溯法的思想、设计与分析

摘要: 回溯法基本思想 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 回溯法思想回溯法是一种在解空间中搜索可行解或最优解的方法。该方法通常将解空间看做树形结构,称为状态空间树。 搜索过程以 DFS

记忆化搜索解决DP过程有效状态值稀疏的问题

摘要: 最优子结构+重复子问题 -> 动态规划 -> 有很多对结果无影响的无效状态 -> 改为记忆化搜索 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算