参考文章：
前言
2023NOI大纲 中，写明了动态规划入门算法为四级难度，属于 CSP-J 的考察范围。
在联合省选 2024 中，D1T3 / D2T1 / D2T2，以及 NOI2024 中，D1T2 / D2T2 都以不同的形式考察了动态规划算法。甚至在 IOI 含金量最高的国际赛事中，动态规划都仍然是受众多选手关注的热门考点。
由此可见，动态规划算法在整个 OI 界都具有格外重要的地位。读者稍微归纳一下可以发现，整个 OI 的热门考点为：DS + 贪心 + DP。
我们常谈动态规划，却难以确定其最准确的概念。动态规划是什么，这是一个很值得思考的问题。
人们普遍认为，动态规划其实是类 DFA 的一种结构，通过递推的方式将自动机上的信息集中于一体。从广义上来讲，递推算法其实也是一种动态规划。
对于一般的动态规划问题，常常需要选手设计动态规划的意义、DFA 的结构以及集中信息的方式，正是如此，就可能出现难易两极偏差较大的情况。
动态规划算法有几个十分明显的特征：
-
无后效性：动态规划可用的必要条件是无后效性。每个状态如果对后续状态都有较大影响，那么我们便难以记录一下这些影响。
-
最优子结构：动态规划的精髓在于将原问题划分为若干个互相独立的子问题。通过合并每个子问题的最优解，从而得到原问题的最优解。
最优化问题
一般而言，DP 可以划分为两种不同的问题：最优化问题 和 计数问题，这里主要探讨最优化问题。
最优化问题，顾名思义，即是在一定条件下，求一个最优性的答案。
说的有点模糊，按 cmd 的话说，就是对于一个集合 \(S\)，每个元素都有一个权值 \(w\)，要求选出一个满足条件 \(p\) 的 \(w(x)\) 最大的 \(x\)。因此，最优化问题都属于组合问题。
如果我们存在
标签：无后效,归纳,算法,问题,Lgx,动态,规划,最优化 From： https://www.cnblogs.com/Sktn0089/p/18371276