Category: 动态规划

2022
算法动态规划

【状态压缩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，等等。实际上在解决

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背包和完全背包题目汇总

优化问题：求最大价值 322. 零钱兑换 474. 一和零 1449. 数位成本和为目标值的最大数字 1049. 最后一块石头的重量 II 组合问题：求方案数(不一定是最优决策) 278. 数字组合 279. 自然数拆分 494. 目标和 377. 组合总和 Ⅳ 组合相同但顺序不同被视作不同的方案 518. 零钱兑换 II 面试题 08.11. 硬币 879. 盈

算法动态规划

背包问题拾遗

背包问题求最优决策方案数 11. 背包问题求方案数 背包问题求具体最优决策方案 12. 背包问题求具体方案 1449. 数位成本和为目标值的最大数字 二维费用 8. 二维费用的背包问题 474. 一和零 280. 陪审团 混合背包 混合背包问题 $1 背包问题求方案数求最优决策序列的方案数是 DP 问题的一种比较常规的后处理问题。求出 dp 信息之后对每个阶段的最优决策数用

算法动态规划

后效性处理

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

算法动态规划

环形DP

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

算法动态规划

二次扫描与换根DP

$0 树形 DP 树形DP $1 不定根树形 DP对于不定根的树形 DP 问题，给定树形结构之后，需要将每个点都视为根进行一轮树形 DP 最终得到结果。 二次扫描与换根法1dp[u] := 整棵树以 u 为根的结果 第一次扫描: 选定一个节点 root 为根，在有根树上进行树形 DP。dpdown[u] := 以 root 为根的有根树上 u 子树的结果 第二次扫描：以 root 为根

算法动态规划

树形背包

分组背包 树形DP $1 分组背包 分组背包 $2 树形背包 10. 有依赖的背包问题 问题有 N 个物品和一个容量是 V 的背包。 物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。 每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价

算法动态规划

分组背包

分组背包问题 分组背包是许多树形DP中状态转移的基本模型 树形背包 $0 分组背包 9. 分组背包问题 问题有 N 组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 分析将组数作为 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

参考：《算法竞赛进阶指南》 0x5 对各维状态进行分阶段，有顺序，无重复，决策性的遍历求解 本文我们系统学习以下动态规划中一些基本概念。这里我们参考《算法竞赛进阶指南》中关于动态规划的讲解，把动态规划的几个核心概念梳理一下，并做一个总结。 本文涉及到的概念可以在以下思维导图查看 动态规划用一句话概括就是对各个状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。 $1 动态规划基础概念(

算法动态规划

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 ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序

算法动态规划

同余类状态

1363. 形成三的最大倍数 1262. 可被三整除的最大和 1262. 可被三整除的最大和问题给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。 算法1：贪心贪心-删数,拼数,选数,改数 算法2：动态规划12345678dp[i][j] := [0..i-1] 上取出若干数的最大和，且和模 3 余 j初始化dp[0][j] = INT_MIN;dp[0]

算法动态规划

推公式优化DP

629. K个逆序对数组 1227. 飞机座位分配概率 1621. 大小为 K 的不重叠线段的数目 1639. 通过给定词典构造目标字符串的方案数 629. K个逆序对数组问题给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。 逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a[i] > a[j]，则其

算法动态规划

自动机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

$0 倍增优化DP 状态线性增长 -> 状态成倍增长 倍增优化 DP 一般分为预处理和拼凑两部分 预处理: 状态成倍增长的 DP，计算出 $2^{k}$ 的状态 dp[k] 拼凑：基于二进制划分思想，用 dp[k] 组合成最终答案 $1 题目466. 统计重复个数 / 294. 计算重复问题由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，[“abc”,3]=

算法动态规划

增删改后的最大子数组和

摘要: 本文介绍最大子数组和的一类变种：可以增删改的情况 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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思想1234dp[u][s] = 常数 u为叶子节点 = f(dp[v1], dp[v2], ...) v1,v2,...为u的子节点s 为与 u 相关的状态答案 g(dp[root]) 有时候子树的答案交给根之后就不会再用到了，这种情况有点像后序遍历处理的问题，此时一般就用后序遍历而不提树形DP的事，例如 树

算法动态规划

货仓选址与安排邮筒

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

算法动态规划

DP问题分类汇总-加强版

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

算法动态规划

股票问题-自动机和动态规划

股票问题机器变种 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 最佳买卖股票时机含冷冻期 714. 买卖股票的最佳时机含手续费 动态规划解各个股票问题，基本问题是 122 和 188 从自动机的角度推导股票问题最抽象的 188 题，最终回到动