Tag: 动态规划

2025
算法动态规划

频繁查询子串是否回文：区间DP

摘要: 频繁查询子串是否回文，用区间DP预处理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在上一篇文章中，我们解决了分割回文串的问题，给定字符串 s，将其分为若干个回文子串，由于需要返回所有可能

算法字符串

频繁查询子串是否回文：Manacher预处理后$O(1)$响应

摘要: Manacher 预处理信息的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在回文的场景中，我们经常会遇到在一个字符串 $s$ 上频繁地给定一个区间 $[i, j]$，问该子串 $s[

算法动态规划

状态转移方程描述最优子结构 | 优化状态表示 | 单调队列优化DP

摘要: 先找到重复子问题，然后通过状态转移方程描述最优子结构 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个动态规划的问题，拿到问题之后，首先手推一两步，看能不能得到规模更小

算法动态规划

树形 DP | 剪枝优化 | 移位操作

摘要: 等效性剪枝优化树形 DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个难题拆解，算法的主框架为树形 DP，第一个难点是发现子树作为阶段需要再加上附加信息才能具备最优

算法算法设计

最少硬币组合问题2：贪心算法【附算法导论习题答案下载】

摘要: 最少硬币组合问题的一种可以贪心的面额集 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在上一篇文章 最少硬币组合问题1：完全背包 中，我们介绍了最少硬币组合问题对任意面额集的通用解法，也就是

算法动态规划

最少硬币组合问题1：完全背包

摘要: 最少硬币组合问题，对任意面额集的动态规划算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 我们此前详细讲解过背包问题，题目的分类汇总参考 01背包和完全背包题目汇总。其中硬币组合是完全背包

2024
算法动态规划

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

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

算法动态规划

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

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

算法动态规划

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

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

算法动态规划

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

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

算法动态规划

减治型区间DP，一个例子

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

算法动态规划

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

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

算法图算法

无向图的最小环问题

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

算法动态规划

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

摘要: 单峰性、二分优化 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

算法疑难杂症

通过不等式优化的算法问题

摘要: 不等式在算法优化中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，不等式经常在解决优化或最值问题时有所应用，例如均值不等式是我们高中时接触过的重要不等式，经常用于解决一些比较简

算法动态规划

剪枝优化DP：基于数学性质排除大量无效决策

摘要: 剪枝策略减少最优决策候选集中的无效决策 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在基于动态规划解决最优性问题时，状态转移方程中，一个状态对应着很多决策。常规的方式是把这些决策都遍历一遍

算法动态规划

无显式结构的动态规划：数列第n项问题

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

算法动态规划

高维状态设计：凸连通块的状态表示

摘要: 凸连通块的状态表示 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个高维线性动态规划的问题，主要难点在于对矩阵中的连通块的状态表示，其中阶段占了一个维度，附加信息占了 5 个维度

算法动态规划

通过离散化处理状态表示中的稀疏维度

摘要: 状态表示中的附加信息要素非常稀疏时，可以用离散化的方式来处理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于动态规划问题，有时仅仅把阶段要素放到 DP 状态中，不足以执行转移。也就是说

算法leetcode

力扣1883-准时抵达会议现场的最小跳过休息次数

摘要: 带上取整的状态转移方程 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个动态规划的问题，整体的思路上还是比较好想的。值得注意的有两个点，一个是状态转移方程中涉及到上取整

算法leetcode

力扣1766-互质树

摘要: 祖先链的信息，树形前缀 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们继续来看一个祖先链和树形前缀的题，在 DFS 的过程中记录祖先链上的质数因子相关的信息。之前的一些文章中

算法leetcode

力扣1997-访问完所有房间的第一天

摘要: 方程组辅助 DP 状态设计，简化思路 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个比较难想的动态规划问题，容易看出是动态规划，但是状态的设计却很复杂，在同一套阶段划

算法leetcode

力扣2642-设计可以求最短路径的图类

摘要: 加边松弛操作 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 Floyd算法 中我们了解到了求最短路径的 Floyd 算法。理解这个算法需要一些动态规划的概念，其中阶段的定义与推导比较

算法动态规划

优先级队列优化 DP

摘要: 优先级队列优化 DP、自定义堆的比较规则 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们解决一个在棋盘上可以向下或向右行动的问题。本题的特点是每一步可以在给定范围内跳格子行动

算法leetcode

【二维线性DP】力扣2312-卖木头块

摘要: 一个二维线性 DP 的比较困难题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们看一个二维线性 DP 的问题。DP 状态有两个维度，这里的两个维度都是附加信息，状态的推导过程

算法leetcode

【棋盘DP】力扣2684-矩阵中移动的最大次数

摘要: 棋盘 DP 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们来解决一个比较基础的棋盘 DP 的问题，以列号 j 为阶段，行号 i 作为附加信息。 题目 2684. 矩阵中移动的最大次数

2023
算法动态规划

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

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

算法动态规划

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

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

算法leetcode

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

摘要: 定式化的动态规划、技巧性的贪心 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 状态大小相同的

算法动态规划

树状数组优化DP：优化问题

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

算法搜索

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

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

算法搜索

记忆化搜索解决DP状态转移方向不好想的问题

摘要: 最优子结构+重复子问题 -> 动态规划 -> 状态转移方向不明显 -> 改为记忆化搜索 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算法。相应地

算法搜索

从递归/搜索出发到记忆化搜索

摘要: 原问题的解依赖子问题的解 -> 先写出递归算法 -> 然后发现有很多重复子问题 -> 增加记忆化 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 记忆化搜索是一种结合了搜索和动态规划的优点的算