决定动态编程的子问题

Question

我已经多次使用了动态编程的技术，但是今天，一个朋友问我如何定义子问题，我意识到我无法提供客观的正式答案。您如何正式定义使用动态编程解决的问题的子问题？

Answer 1

动态编程的原理是自上而下（即递归），但要自下而上。因此，设计DP的一个好策略是递归制定问题并以这种方式产生子问题。

Answer 2

正如@suresh所指出的那样，一旦您知道您的问题可以通过DP解决（即它表现出最佳的子结构和重叠的子问题），您可能会想到一个分歧和征服递归解决方案。

当然，划分和征服将是高度不足的，因为即使已经找到并解决了相关递归树中遇到的每个子问题，也将再次解决。这就是DP的不同之处：每次遇到子问题时，都可以解决并将其解决方案存储在表中。稍后，当您再次遇到该子问题时，您可以访问$ Mathcal {o}（1）$ time的解决方案，而不是再次求解它。由于重叠子问题的数量通常由多项式界定，并且解决一个子问题所需的时间也是多项式（否则DP无法提供具有成本效益的解决方案），因此您可以在多项式解决方案中实现。

因此，考虑鸿沟和征服解决方案将为您提供有关您特定问题的子问题的见解。

Answer 3

我的经验是找到一种方法，可以“通过存储已经列举的有用价值来减少冗余的枚举”。顺便说一句，动态编程在ICPC（国际大学编程竞赛中确实很受欢迎。在练习几个ICPC问题之后，任何人都可以对DP有自己的感觉。