RT，因为只是单纯记录，所以很多地方不会严谨说明，也不会很长。（不过主要还是凭自己的记忆） 
可以当兴趣书看。 
有时间可能会逐渐完善吧 
参考 oi.wiki 和 算法竞赛 
请确保您有足够的前置知识。 

正文
引入
dp 全称 动态规划（Dynamic Programming, DP）。顾名思义，它是一种实时解决问题，规划问题的一种思想，类似贪心，但是重点在规划。 
严格来说，动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 
对于一般人而言，是很难自主，不经过外界帮助去想到这种方法的，后面会有所提到。 
基础
[IOI1994] 数字三角形 
 [image] 
一般的思路是暴力枚举所有可能的路径，并选取最优解。 
通过简单计算可得，路径条数是 n! 的，无法接受。 
考虑我们从上往下走是怎么做决策的。 
如果我们需要往右下方走，那这代表左下方能产生的最大...