线性动态规划规划简介 在所有动态规划中，线性动态规划的难度最低，同时线性动态规划也是所有动态规划的基础。 顾名思义，线性动态规划就是说动态规划的过程在“一条线”上进行，状态转移只有一个方向。最常见的线性$\rm{DP}$有子集和问题，$\rm{LIS}$问题，$\rm{LCS}$问题，字段和问题等。其实，线性$\rm{DP}$的用处不只如此，很大一…

背包问题简介 背包问题解释 背包问题是动态规划中的经典问题，本节中会讲到多种背包问题，并对各种背包问题进行优化与转化。背包问题是指在一个有容积或者重量限制的容器中放入物品，每一个物品有不同的重量、容积、价值，要求在容器的承受范围内取得的价值最大。根据物品的限制条件不同，背包问题可以分为$01$背包、完全背包、多重背包、分组背包和混合背包问题。 背包…

动态规划简介 动态规划是理查德·贝尔曼与$1957$年提出的一种方法，他把原问题分解成若干个小问题，自底向上先求解最小的子问题，把结果存储在表格中，求解大的子问题时直接从表格中查询小的子问题的解，以免重复计算，从而提高效率。 动态规划性质 最优子结构 子问题重叠 无后效性 最优子结构是指问题的最优解包括其子问题的最优解。 子问题重叠指的是每次分解出…

传送门 题目理解与强调 精简一下题意：本题给出一个字符串，在无视非字母、字母大小写的情况下，字符串 helloword 出现的次数。 题解 读入问题 在无其他问题的情况下，依然过不了，可以尝试我这一套读入程序。 char c; while((c=getchar())!=EOF){ } 解决主体问题 问题很简单，从第一个数字枚举整个字符串，先除去非字…

在一个图中进行DP，对于部分题目来说随意一个顺序会破坏DP的无后效性原则，例如题目”洛谷：P3387 【模板】缩点“中，需要找出DAG中的一条路径，且这条路径上的点权和最大。我们需要从枚举的第一个点开始，记录$ dp[i] $，表示从第一个点到当前节点的最大点权和，每次向下枚举一个点，都需要保证我们要枚举的这个点的入度为$0$，即保证它不会再被其他…