Category: 动态规划

2024
算法动态规划

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

摘要: 分析问题的过程猜出最优子结构 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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

算法动态规划

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

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

算法动态规划

剪枝优化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 状态中，不足以执行转移。也就是说

算法动态规划

优先级队列优化 DP

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

2023
算法动态规划

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

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

算法动态规划

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

摘要: 不相邻的子序列最大 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 在文章 股票系列问题-高维动态规划 中我们从高维动态规划的角度讨论了股票问题这个系列问题。 如果把操作

2022
算法动态规划

【状态压缩DP】N次操作后的最大分数和

摘要: 一道状态压缩DP的简单题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 状态压缩DP 中我们学习了状态压缩DP的知识，本文我们来看一个相关的经典问题。 题目

算法动态规划

分汤-概率DP与浮点数精度处理结合

摘要: 一道概率 DP 的问题，记忆化搜索 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，前面我们详细学习过概率 DP 这类算法，参考文章 概率DP。【力扣808. 分汤】是力扣上比较少见的

算法动态规划

多米诺与托米诺骨牌平铺：矩阵快速幂优化DP

摘要: 动态规划解决计数问题，模下矩阵快速幂优化 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，之前在文章 计数DP 中我们总结了常见的使用动态规划解决计数问题的题目，在文章

算法动态规划

目标带绝对值的处理：最大子数组和的绝对值

摘要: 本文介绍最大子数组和的一类变种：和最大改为和的绝对值最大 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个

算法动态规划

【树形DP】树的直径

摘要: 力扣 1245, 1522，树的直径，最经典的树形 DP 题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，我们继续研究力扣秋季赛的题目。在十一之前参加了力扣秋季赛个人赛，

算法动态规划

状态压缩DP

摘要: 本文介绍状态压缩 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文参考《算法竞赛进阶指南》 0x5，书中关于状态压缩 DP 的讲解我觉得非常好。之前虽然解决过很多状态压

算法动态规划

博弈DP

摘要: 本文介绍博弈 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 博弈是应用数学的一个分支，表示在多决策主体之间行为具有相互作用时，各主体根据所掌握信息以及对自身能力的认知，做

算法动态规划

期望DP

摘要: 本文介绍期望 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 与概率DP类似(参考文章概率DP)，期望DP不是一种特殊的动态规划类型，而是一种常见的应用场景。类似的还有计数

算法动态规划

概率DP

摘要: 本文介绍概率 DP 的原理和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 概率DP并不是一种特殊的动态规划类型，而是一种常见的应用场景。类似的还有计数DP，博弈DP，等等。实际上在解决

2021
算法动态规划

矩阵快速幂及其动态规划优化中的应用

摘要: 本文介绍矩阵快速幂的算法原理与代码模板，并解决一个例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 多米诺与托米诺骨牌平铺 中，我们用矩阵快速幂优化 DP 的方式解决了一个计数问题

算法动态规划

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

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

算法动态规划

前缀和优化DP

摘要: 本文介绍了动态规划的一种优化方法：前缀和优化 DP。并拆解了力扣第 1871 题。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 前缀和优化 DP当 DP 转移方程是如下形式的时候： 计算

算法动态规划

最大子矩阵和

摘要: 最大子矩阵和问题，有两种处理二维情况的方式。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解

2020
算法动态规划

01背包和完全背包题目汇总

摘要: 转换为 01 背包和完全背包的组合问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 组合数学的问题有时候可以转换为背包问题进而解决，而组合数学研究组合的存在性、计数性、优化性。也就是说背包

算法动态规划

背包问题拾遗

摘要: 背包问题的遗留问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 01背包和完全背包 和 01背包和完全背包题目汇总 中我们分别了解了 01 背包和完全背包的算法原理、代码模板，以及

算法动态规划

局部后效性的处理

摘要: 有后效性：状态之间互相转移，互相影响。无法确定合适的阶段。 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 有后效性问题的背景阶段是 DP 的三要素之一，无后效性是 DP 算法有效的三个

算法动态规划

环形DP

摘要: 环形结构上的动态规划 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings $0 环形结构上的 DP对于环形结构上的 DP，比较直接的思路是： 通过枚举法，选择一个位置将环断开，变成线性结构后进行线

算法动态规划

二次扫描与换根DP

摘要: 无根树上的树形DP，二次扫描与换根的处理方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 树形DP 中，我们简要介绍了树形 DP 的思想，以及列举了很多可以解决的问题。 在有的问题

算法动态规划

树形背包

摘要: 树形背包 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一：树形背包。树形背包问题是 树形DP 和 分组背包 的应用。 树形背包问题 10. 有依赖

算法动态规划

分组背包

摘要: 分组背包 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以一个模板题看一下背包问题的变种之一：分组背包。分组背包是树形背包的基础，同时也是很多树形 DP 中状态转移的基本模型。 分组