求dp刷表法讲解（我是蒟蒻勿喷）

Question

我在搜这一题时，遇到了这玩意——刷表法，然后……就蒙了，这是什么东西啊？求神犇讲解，细致一点~

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/891417
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：【简单dp】舔狗舔到最后一无所有
• 除此之外, 这篇博客: 饼干【贪心确定序列】【类似整数划分DP】【记录中间状态，递归输出路径】中的 饼干 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  n个孩子，m个饼干。每个孩子都有一个嫉妒值，嫉妒值=（有多少个孩子的饼干比他多）* g。

  求一种分配方式，使得总体嫉妒值最小

• 以下回答来自chatgpt:

  背景

  DP即动态规划，它是求解多阶段决策过程最优化的方法。DP刷表法与DP递归法为动态规划的两种实现方式。由于递归法的启发式搜索特性，其无法避免重复搜索与无脑递归的缺陷，因此DP刷表法是一种比较重要的实现方式，其优点为空间复杂度小，并且采用了序列化的技术，提高了效率。

  基本概念

  DP刷表法指根据问题的要求，确定题目的状态，之后设计状态转移方程之后，通过表格的形式存储状态转移的过程，并以串行的方式遍历表格从而求解最优化的问题。该思想就如同处理Excel表格数据的方式，仅仅向下和向右遍历每列和每行的数据，这一方向单一性的特点极大地节约了算法的时间开销。DP刷表法也是整个DP算法中的核心思想。

  运作流程

  DP刷表法的基本流程为：

  • 划分状态，抽象问题；
  • 定义状态间的关系，设计状态转移方程，并转移；
  • 利用表格刷表动态规划的过程；
  • 构造最优解。

  具体操作

  1. 确定状态及定义状态间的关系

  动态规划的核心是状态的确定和状态间关系的妥善设计。状态指的是描述问题的状态量，可能是一个自变量或者自变量的集合。状态间关系，指假定已经求解出某些变量，在此基础上通过一定方式，求出当前变量的取值和推导出下一状态。通常可以使用后序方式求解状态转移表，其中包括过程和结果两个部分。

  1. 设计状态转移方程

  在画出状态转移表之后，根据当前状态，定义新的状态与新的目标变量之间的联系。这一过程被称为状态转移。状态转移使用状态转移方程完成。

  $$ f_{i,j}=max{ f_{i-1,j} ,f_{i-1,j-w_i} +v_i}$$

  其中，$f$代表状态空间；$i$，$j$是状态空间的两个状态。状态转移时需要有定义好的方程，才能快捷地计算出每一个状态的值。

  1. 利用刷表法处理状态

  状态转移完成后，就开始了处理状态的过程。实际上，在这个过程中，问题已经得到了求解。

  当状态间的关系确定之后，采用条件递推，逐个遍历表格元素（不仅仅局限于仅遍历状态空间），在符合条件的情况下，更新元素的值。为避免状态间的影响，通常采用两个循环遍历刷表。对于每一个元素，它的值受所有可达到它状态之间的状态的情况影响，因此计算出状态转移表之后，应该重新遍历该表来完成最终求解。

  1. 构造最优解

  得到的最后的数表中仍有多个数据，仍需要从中找到最佳解决方案，此时可以分类讨论选择方法并判断。通常从表格中得到最优解，可以直接逆推而得。

  注意事项

  DP算法虽然能在一定程度上减少运算量，但通常会导致额外开销。因此，为保证算法的性能和保证算法不会无头绪的扩大开销，需要控制总状态数，引用外部数组，符号表等。此外，算法的复杂程度也使得该算法敏感于小细节。因而算法的设计和实现能力对程序的质量至关重要，对程序代码的调试过程中应格外小心。

  参考资料

  • 动态规划刷表法
  • 动态规划刷表法：最值前的路径整数问题

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^