algorithm - 如何为动态规划算法找到合适的公式

Question

我正在阅读动态规划。我读到要擅长它，需要实践和直觉，但这个建议对我来说似乎很笼统。
对我来说最难的部分是找出一个递归公式。有时，解决方案中使用的公式对我来说似乎并不那么直观。
例如，我阅读了以下问题:

You have 2 strings S and T. Give an algorithm to find the number of times S appears in T. It is not mandatory for all characters of S to appear contiguous in T.

解决方案基于以下递归公式，这对我来说一点都不直观:

Assume M(i, j) represents the count of how many times i characters of S appear in j characters of T. Base cases:
i) 0 if j = 0
ii) 1 if i = 0

我想知道是否有某种问题的“分析”可以帮助定义/找到正确的递推公式来通过 DP 解决问题？

Answer 1

维基百科上描述的很好，here :
“在数学、计算机科学和经济学中，动态规划是一种通过将复杂问题分解为更简单的子问题来解决它们的方法。它适用于表现出重叠子问题和最优子结构(如下所述)属性的问题。适用时，该方法比原始方法花费的时间少得多。”

另请阅读重叠子问题和最优子结构。