[算法笔记2]动态规划

关于动态规划的一些新感悟。
自从这学期学校开设了算法课之后，受到算法课老师的鼓励我突然又有了写算法题的动力。特别是老师第一节课重新回顾的动态规划算法，使我对动态规划有了一些新的理解。

其实之前我一直对动态规划有一种说不出来的敬而远之地感受。我最早接触动态规划算法可以追溯到高中的时候了，那个时候去少年宫学各种算法(顺便和小伙伴们愉快的玩耍)，记得学到最短路径的dijkstra算法，当时学了之后不由感叹，哇！还能想出这样的算法，也太强了吧！这怎么想得出来嘛！所以从那个时候起我每次知道某道题要用动态规划去求解时总会不由自主地头大。因此其实很长一段时间以来，我的动态规划的水平仅仅停留在最粗浅的三角形路径最大问题上(就是那个很naive的给一个三角形让你求一条路径使得从左上角到右上角权值和最大)。

当然也有很多小伙伴和学长学姐告诉过我，动态规划的方程式要满足三个特性，什么最优子结构，无后效性，子问题重叠，我都能熟练背诵了。但是知道这三个特性又有什么用呢，大多数情况下，我要么不知道如何表示状态，要么不知道如何写出方程式。当然写不出来方程式，我就会去看题解，看它的方程式，然后看了方程式就会实现了，但是看完写完了AC了，之后如果过一段时间再去会过来看这道题，我八成又忘记当初的那个方程式了。

所以我冥冥之中总觉得，我不能说不会动态规划算法，我也能大致理解动态规划算法的原理，但我可能一直缺少某种方法或者工具，导致在实际做题时始终无法得到正确的求解状态和方程式。

不过在听了上一周的算法课之后，我总算顿悟了一些东西！虽然，我不能保证今后碰到的所有动态规划题目我肯定全部能做出来，但我至少在动态规划问题上面增长了不少的信心。长久以来，我一直对动态规划的方程式有很多疑问。为什么方程式是这么写的？为什么有些方程式要从左边和右边分别计算，有些方程式只需要计算一边？为什么写方程式的时候只要考虑当前的状态就行了？为什么考虑了当前的状态整个问题就能解决了？怎么样才能写出合理的方程式呢？

老师在课上介绍动态规划算法的时候非常简单，几乎是举了一个例子之后就跳过了，不过我从这个例子中学到了动态规划算法的本质，那就是：填表。

可能有些人看到这里要失望了，我卖了这么大的一个关子，结果居然就是两个字填表。但事实是，在上这节算法课之前我完全不了解动态规划居然和填表有密切的关系。在填表的过程中，你可以逐渐了解到表中的每个数字是如何计算出来的，而列出动态规划方程的本质其实就是弄清楚表中每个格子的数字是如何被计算出来的，存在怎样的依赖关系。你也许一开始无法直接写出方程式，但通过在表格中的填数，你可以慢慢冷静下来，一步一步的去思考表格中每个数字的形成过程，这实质上也正是动态规划方程的状态转移过程以及它们的递归关系。想清楚怎么填表，也就想清楚了怎么写方程式。

你也许还会有疑问，很多动态规划的问题不仅仅是二维的，有时候甚至是三维的，四维的，这个时候怎么填表呢？我相信，在熟练掌握了二维的动态规划后，你其实不必真的写一张二维的表格。你只要在心中默默地有一张表格，想清楚状态之间的递推和依赖关系，就能很自然的写出方程式了。

最近完成的几道dp题目:

• 乌龟棋
  • $pos \leftarrow i+j \times 2+k \times 3+l \times 4$
  • $dp[i+1][j][k][l]=dp[i][j][k][l]+s[pos+1]$
  • $dp[i][j+1][k][l]=dp[i][j][k][l]+s[pos+2]…$ 以此类推
• Codeforces 1114D. Flood Fill
  • $dp[l-1][r][0]=\min \{ dp[l][r][0] + diff(a[l - 1], a[l]), dp[l][r][1] + diff(a[l - 1], a[r]) \} $
  • $dp[l][r+1][1]=\min \{ dp[l][r][1] + diff(a[r + 1], a[r]), dp[l][r][1] + diff(a[r + 1], a[l]) \} $
• Codeforces 1132F. Clear the String
  • $dp[l][r] = \max \{1 + dp[l + 1][r], \min \limits_{l < k \le r, s_k = s_r} dp[l + 1][k - 1] + dp[k][r] \}$

最后，祝每个人在做动态规划题时能做到：眼前无表，心中有表。