区间 DP（Interval Dynamic Programming）是动态规划的一种特殊形式，其状态通常以区间的左右端点来定义，即dp[i][j]表示区间[i...

在开始具体模型之前，我们先统一一个核心认知：所有背包扩展模型，本质都是基础背包的 “规则变种”。

通俗来讲，背包问题的本质是 “有限资源下的最优选择”。想象一个场景：你有一个容量有限的背包，面前有一堆物品，每个物品都有自己的重量（或体积）和价...

在正式讲解之前，我们先明确：为什么 LIS 和 LCS 能被称为 “经典线性 DP”？

在正式学习之前，我们先聊聊为什么很多人觉得动态规划难。其实主要原因有三点：

2026-01-11：三段式数组Ⅱ。用go语言，给定长度为 n 的整数序列 nums，要求选出一个包含至少四个元素的连续区间 [a, b]（0 ≤ a < b ...

前言 1400分即为一个分水岭，相关题目需要思维与较强代码能力，我本人也是困在这个分水岭一段时间了，并且相关题解对于新手来说很不友好，可能会用到c++17，甚...

对于动态规划，求解当前目标的状态dpi，则依赖于前期的状态（dpi-1或者dpi-1）。对于目标值amount，则依赖于amount之前的值，因此需要遍历遍历1...

该算法的巧妙之处在于通过二分答案将最大化瓶颈值的问题转化为一系列判定问题，并利用DAG的拓扑序特性，在每次判定时使用动态规划来高效地检查是否存在总成本满足约束的...

dp[i][j]表示从前i个物品中选，总价值不超过n，并且使得每件物品的价格与重要度的乘积的总和最大。

前提：在这里用 x表示满足nums[i]%3==1数，用 y表示满足nums[i]%3==2的数。

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，这两堆石子的总和记为本次操作的代价。问：将N堆石子合并成一堆石子的...

最后，返回值，返回dp表最后一个值，表示以字符串最后一个字符结尾，是否可以拼接成功。 

状态转移方程的推导： 当s[i]!=s[j]时，也就是子串的第一个字符和最后一个字符不相等，那么肯定不是回文串，所以dp[i][j]=false。 当s[...

有一个价格数组prices，表示第i天的股票价格为prices[i]，整个过程只能买入股票和卖出股票一次。并且买入股票必须再卖出股票之前。

本题求解的是最长子序列，需要明白的是子序列是不连续的。通过动态规划来解决时需要清楚变量i、dpi数组的含义，理解递推公式的含义：dpi=max(dpj+1,dp...

以上就是动态规划的一些基本例子，还有一个例子我没有写上来，就是带有记忆功能的动态规划技术解决背包问题。后面有时间我会补上。

在编程竞赛中，计数类动态规划常结合“状态转移+区间扩展”的思路，解决序列构造的方案数问题。本文以“事件序列的跌宕起伏排列”为例，拆解这类问题的分析逻辑、实现步骤...