Tag: DP的优化

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 在基于动态规划解决最优性问题时,状态转移方程中,一个状态对应着很多决策。常规的方式是把这些决策都遍历一遍

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

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

优先级队列优化 DP

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

优化状态表示,降低状态转移的复杂性;LCIS问题

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

树状数组优化DP

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

力扣LCP14-切分数组

摘要: LCP14,分解质因数+哈希表优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个分解质因数与动态规划结合的题。直接写出动态规划算法比较简单,但难点在于如何用分解质因数进行优化

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

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

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

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

【连载】动态规划的优化

摘要: 关于动态规划的优化的文章 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本系列连载是关于动态规划的各种优化方法的。动态规划有很多种优化方式,比较常见的如下图所示 关于动态规划本身,可以参考

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

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

前缀和优化DP

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

leetcode第242场周赛:前缀和优化 DP 专场

摘要: 本文是 leetcode 第 242 周赛的记录。主要涉及的算法包括双指针、值域二分、队列、动态规划、前缀和、博弈。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 总览这是 leetcode

leetcode第241场周赛:状态定义不变,优化状态转移方式

摘要: 本文是 leetcode 第 241 周赛的记录。主要涉及的算法包括枚举子集、分类讨论、设计、动态规划、组合数学。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 总览这是 leetcode

单调队列优化多重背包

摘要: 单调队列优化DP 应用在多重背包问题上 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 多重背包及其二进制划分优化 中我们了解了多重背包问题,以及使用二进制划分的思想来减少状态个数的做法,

【DP难题】力扣1639-通过给定词典构造目标字符串的方案数

摘要: 一道推公式优化 DP 的问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们看一个推公式优化 DP 的问题。本题是第 37 双周赛 D 题。关于推公式优化 DP 的更多例子,

单调队列优化DP

摘要: 单调队列优化 DP 的思路以及一些例子 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 使用数据结构优化动态规划的状态转移过程是很常见的思路,例如 平衡树优化DP、哈希表优化DP。单调队列也是

单调队列

摘要: 单调队列的算法原理,代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文详细介绍单调队列的算法原理、代码模板和应用。涉及到的题目汇总如下: 基本模型 239. 滑动窗口最大值

同余类分解状态优化DP

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

推公式优化DP

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

哈希表优化DP

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

在模拟过程中找出循环节

摘要: 循环节优化模拟;倍增优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在模拟的过程中,如果出现了循环节,就可以直接跳过很多中间的模拟步骤。有时这种循环节是现成已知的,例如文章 通过已知

倍增优化DP

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

稀疏表(倍增优化DP):区间最值问题

摘要: 元素不变的区间最值问题,稀疏表 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 给定一个数组,其中的元素可以修改,要查询数组中某个区间的和。过程中需要维护元素修改的操作,并且要高效查询区间的和

货仓选址与安排邮筒

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

DP问题分类汇总-加强版

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