Category: 动态规划

股票问题-自动机视角(自动机DP)

摘要: 本文介绍股票系列问题,从自动机的角度理解 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 股票系列问题-高维动态规划 中我们从高维动态规划的角度讨论了股票问题这个系列问题。 如果把操作

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

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

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

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

多米诺与托米诺骨牌平铺

摘要: 动态规划解决计数问题,模下矩阵快速幂优化 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的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,等等。实际上在解决

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

摘要: 本文介绍矩阵快速幂的算法原理与代码模板,并解决一个例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解

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

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

背包问题拾遗

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

后效性处理

$0 有后效性问题的背景阶段是 DP 的三要素之一,无后效性是 DP 算法有效的三个前提之一。参考 动态规划概念和基础线性DP 在一些问题中,抽象出状态维度,并设计出状态表示和状态转移方程后,可能会发现这样的状态设计不满足无后效性,部分状态之间互相转移,互相影响,构成了环形。 对于环形问题,有一种【可拆解的环形问题】,这样的问题是可以拆环后转化成线性结构上的 DP 问题,参考: 环形DP 。 而对

环形DP

环形结构上的DP 枚举断开位置,求解对应的线性结构上的DP 可拆解的环形DP问题 两次DP 288. 休息时间 213. 打家劫舍 II 1388. 3n 块披萨 复制一倍接在末尾 283. 多边形 变为 2N 长线性数组后用区间DP 289. 环路运输 变为 2N 长线性数组后用单调队列 918. 环形子数组的最大和 算法1: 复制一倍接在末尾 + 前缀和+单调队列 算

二次扫描与换根DP

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

树形背包

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

分组背包

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

单调队列优化多重背包

01背包和完全背包 多重背包 同余类状态 单调队列 单调队列优化DP $0 6. 多重背包问题 III有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。 120<N<=10000<V<=20000 $1 多

双串线性DP,二维状态表示阶段

子序列匹配 392. 判断子序列 115. 不同的子序列 字符串模糊匹配 72. 编辑距离 712. 两个字符串的最小ASCII删除和 583. 两个字符串的删除操作 44. 通配符匹配 10. 正则表达式匹配 其它 97. 交错字符串 727. 最小窗口子序列 1458. 两个子序列的最大点积 $0 双串线性 DPdp[i][j]: i

最长公共子序列LCS

最长公共子序列 1143. 最长公共子序列 1035. 不相交的线 最长公共子串 718. 最长重复子数组 求具体的最长公共子序列 1092. 最短公共超序列 $1 最长公共子序列线性DP, 是动态规划中最常见的一个类型. 相比其它类型的DP, 它的状态设计变化非常多. 其中最经典的问题是 LIS, LCS, 它们分别代表了单串和双串的线性 DP 中最经典的状态表示和阶

棋盘DP

摘要: 棋盘 DP 的题目总结 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在很多时候,我们要在矩阵或者三角形上解决问题。比如给定一个矩阵,求最大的子矩阵和;又比如给定一个三角形,求从第一行走

单串线性DP-多维状态,在阶段的基础上附加维度

801. 使序列递增的最小交换次数 1187. 使数组严格递增 873. 最长的斐波那契子序列的长度 1027. 最长等差数列 813. 最大平均值和的分组 887. 鸡蛋掉落 256. 粉刷房子 265. 粉刷房子 II 975. 奇偶跳 403. 青蛙过河 1478. 安排邮筒 1230. 抛掷硬币 410. 分割数组的最大值 1473. 给房子涂色 III 446. 等差数列划分 II -

单串线性DP-一维状态表示阶段

32. 最长有效括号 413. 等差数列划分 91. 解码方法 338. 比特位计数 871. 最低加油次数 978. 最长湍流子数组 656. 金币路径 1024. 视频拼接 639. 解码方法 2 1578. 避免重复字母的最小删除成本 1218. 最长定差子序列 1235. 规划兼职工作 1043. 分隔数组以得到最大和 1416. 恢复数组 1055. 形成字符串的最短路径 368

最长上升子序列LIS

最长上升子序列 300. 最长上升子序列 DP (单串线性DP基本设计思路) (权值)树状数组优化DP 二分 (LIS 的最优解) 最长上升子序列的基础变形 最长上升子序列个数 673. 最长递增子序列的个数 最长上升子串 (最优解是滑动窗口) 674. 最长连续递增序列 俄罗斯套娃信封 (通过合适的排序转换为 LIS) 二维 354. 俄罗斯套娃信封问题

有向图上的DP(HMM前向后向计算)

$0 有向图上的 DP (HMM前向后向计算)一些表现形式为有向图 D 上的动态规划的问题,其阶段的推导是在 G 上进行的,如果本阶段在节点 u,u, v 之间没有有向边,则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段,而是作为阶段持有的状态。而阶段另有一个维度表示,并且具有例如长度,时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

无向图上的DP(CRF前向后向计算)

$0 无向图上的 DP (CRF前向后向计算)一些表现形式为无向图 G 上的动态规划的问题,其阶段的推导是在 G 上进行的,如果本阶段在节点 u,u, v 之间没有无向边,则下一个阶段是无法到 v 的。 一般情况下图的节点不直接作为阶段,而是作为阶段持有的状态。而阶段另有一个维度表示,并且具有例如长度,时间这样的意义。DP 方程具有以下形式 12dp[v][i] = f(v, i, dp

高维线性DP,多维状态,阶段+附加维度

单串线性 DP 没有附加状态: 单串线性DP-一维状态表示阶段 增加一维状态 单串线性DP-多维状态,在阶段的基础上附加维度 增加多维状态 1420. 生成数组 股票问题-自动机和动态规划 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 最佳买卖股票时机含冷

LIS和LCS拾遗,LCIS

LIS 基础 LCS 基础 LIS 划分 dilworth 定理 变形 LCS 转 LIS LCIS 优化1: 对状态表示和阶段划分的优化 优化2: 代码等价变形 $0 LIS 和 LCS 基础 最长上升子序列LIS 最长公共子序列LCS $1 LIS 划分问题给定一个数组,可以将其划分为若干个上升子序列,求划分的上升子序列的最少的个数。 分析Dilworth 定理及其对偶定理:

动态规划概念和基础线性DP

摘要: 动态规划的基本概念 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们系统学习一下动态规划中一些基本概念。这里我们参考《算法竞赛进阶指南》中关于动态规划的讲解,把动态规划的几个核心概念梳

DP方程组

$0 DP 方程组 两个 DP 方程 f[i] 和 g[j] 推导状态的时候是同时推进 i,j f[i] 可能与 f[i - 1] 和 g[j] 都有关 g[j] 可能与 g[j - 1] 和 f[i] 都有关 i 和 j 的具体推进方式和细节需要注意 $1 题目1537. 最大得分12345678910f[i] := 推进到 nums1[i-1] 的最大和g[j] := 推

单调队列优化DP

1425. 带限制的子序列和 单调队列优化DP单调队列优化 DP 的转移方程的形式 dp[i] = \min\limits_{L(i)其中 f(i, j) 可以分为仅与 x 相关和仅与 y 相关的两部分: f(i, j) = g1(i) + g2(j) 1425. 带限制的子序列和问题给你一个整数数组 nums 和一个整数 k ,请你返回 非空 子序列元素和的最大值,子序列需要满足:子序

同余类分解状态优化DP

摘要: 同余类分解状态优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通过两个力扣的题目看一下通过同余类分解状态的方式优化 DP。此外这两个问题都另外有贪心和自动机的解法。 同余类分解状

推公式优化DP

摘要: 一些可以通过推公式优化动态规划算法的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 通过分析问题列出的动态规划的转移方程,有时经过一些公式推导后可以简化,这也是一种可以优化动态规划算法的

自动机DP

552. 学生出勤记录 II 935. 骑士拨号器 1220. 统计元音字母序列的数目 1641. 统计字典序元音字符串的数目 1223. 掷骰子模拟 1220. 统计元音字母序列的数目问题给你一个整数 n,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串: 字符串中的每个字符都应当是小写元音字母(’a’, ‘e’, ‘i’, ‘o’, ‘u’) 每个元音 ‘a’

哈希表优化DP

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

平衡树优化DP

1235. 规划兼职工作 975. 奇偶跳 1235. 规划兼职工作问题你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。 给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大

多重背包

$0 多重背包问题描述有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价值。 $1 多重背包朴素解法状态设计从 01 背包入手01背包的状态 1dp[j] = 总体积为 j 时,最大价值 01 背包的转移 1dp[j] = max(dp[

DAG上的DP

拓扑序(DFS 序 / BFS 序) 转移 dp[u] = f(dp[v]), u, v 是拓扑序的关系 按照 BFS 拓扑序推导还是按照 DFS 拓扑序推导需要根据需求来分析。 BFS 拓扑序 DP dp[v] := 以 v 为终点... 拓扑序: 计算 dp[v] 时,所有父节点 u 的 dp[u] 已经计算完 DFS 拓扑序 DP (记忆化搜索) dp[u] := 以 u 为起点...

倍增优化DP

摘要: 倍增优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 倍增法 中我们了解了倍增法的原理与实现。本文我们以力扣 466 来看一下倍增优化 DP,最后我们解决一个非常困难的问题。

增删改后的最大子数组和

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

区间DP

区间 DP 分治型 减治型 减治型区间DP题目 5. 最长回文子串 647. 回文子串 486. 预测赢家 516. 最长回文子序列 1147. 段式回文 730. 统计不同回文子字符串 1312. 让字符串成为回文串的最少插入次数 1216. 验证回文字符串 III 1278. 分割回文串 III 分治型区间DP题目 312. 戳气球 471. 编码最短长度的

排列计数

526. 优美的排列: 状态压缩DP求满足条件的排列方案数 搭积木问题: DFS + 剪枝,枚举所有满足条件的排列,一个一个计数 装饰围栏: 线性DP求满足条件的排列方案数 + 康拓编码求若干排列的字典序第K大 $1 526. 优美的排列算法:状态压缩DP1234dp[state] := 当前使用数字为 state(状态压缩) 情况下的排列dp[0] = 1状态转移: 枚

计数DP

摘要: 本文简要介绍一下计数类的问题,以及 leetcode 上的相关题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 计数是组合数学的重要内容。不考虑用母函数等手段求解析解的话,计数问题一般有

树形DP

摘要: 树形DP的思想与经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 树形DP思想 在树形结构上求解问题,在某棵以 u 为根的树上的答案为 dp[u],其重复子问题是子树上的问题,对应的答

货仓选址与安排邮筒

摘要: 安排邮筒问题,使用动态规划解决 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天看一个非常经典的动态规划的问题,本题是第 28 双周赛 D 题,安排邮筒。 安排邮筒说的是

DP问题分类汇总-加强版

摘要: 文章《dp问题分类汇总》的加强版 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings dp问题分类汇总 的加强版,《动态规划精讲》 系列的目录结构的主要参考。题目主要是 2000 以内的。 1、