Archive: 2024/6

减治型区间DP,一个例子

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

问题的拆解、抽象与转化

摘要: 将新问题转化为已经解决过的老问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 当我们拿到一个新问题时,一个重要的思想是将其转化为已经解决过的老问题。具体的转化方法需要结合具体问题,比较有技

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

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

反悔贪心:每天可以买进一股/卖出一股/不操作的股票问题

摘要: 反悔贪心的一种实现:通过精巧的公式设计,跟着贪心策略可以自动执行反悔 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 反悔贪心与反悔堆的思想,带截止时间的任务选择问题 中我们介绍了反悔

偷k个房间的打家劫舍问题:双向链表维护的反悔贪心策略

摘要: 贪心过程自动反悔的精巧设计 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们继续看一个反悔贪心算法的精巧设计。本题首先比较容易想到一种贪心思路,但有些问题,需要反悔机制进行纠正

反悔贪心与反悔堆的思想,带截止时间的任务选择问题

摘要: 反悔贪心的思想,带截止时间的任务选择问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对于具有最优子结构的问题,如果整体最优解可通过一系列局部最优解的选择达到,并且每次选择可以依赖以前作出

系数均为1的线性不定方程解的个数:母函数与容斥原理

摘要: 母函数+容斥原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 设 $a_{1}, a_{2}, \cdots, a_{n}$ 为非零整数,$b$ 为整数,关于未知数 $x_{1}, x_{