关于动态规划的思考[特殊字符]

动态规划题我接触已经有些时间了，平常在洛谷刷题时老的题型用模板写也能ac，但只要出现新题型我就想不出来，看题解就有一种好像确实就该这么写，实际上自己还是没有真正掌握，缺少对dp的深入思考。

事实上，动规题型核心是把问题简单化，就比如说我收藏夹线性dp第一道那个三角形的题，初读题目感觉有点复杂，路径那么多，怎么找到权值最大的路径呢？产生这种感觉的原因在于自己把问题想当然的以全面复杂的角度来看了，比如自动把它直接看成n层来处理，我们可以简单来看他，多层的确不好直接处理，但是如果只有两层呢？从第一层走到最底下的第二层，找权值和最大的是不是简单了，这样我们便能确定第一层for循环该怎么写，倒序从n-1层，一直便历到第一层，那每一个i又该如何处理？我们要知道，我们在处理i时，意味着i-1以前的信息我们全知道了，也就是如果要处理从i层到n层，那么底下面的层我们全都已经处理好了，那能否利用这个条件来推导出递推公式呢？显然也可以吧？递推公式只要能想出来，第二层for循环也就出来了，题目已经基本解决了。

一定要记住，动态规划的核心步骤永远是先把问题规模缩小看能否处理，然后看看能否在逐步扩大规模的过程中利用之前已经处理好的信息来写出递推公式，最后问题规模一直到题目所需，答案也就递推了出来。

基本都是这样来思考，例如那道租船问题，以及最长上升子序列。