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

Question

我正在阅读有关动态编程的信息。我读到它才能精通它，需要练习和直觉，但这个建议对我来说似乎很笼统。
对我来说最难的部分是找出一个递归公式。有时，解决方案中使用的公式对我来说似乎并不那么直观。
例如，我阅读了以下问题：

你有 2 个字符串 S 和 T。给出一个算法来找出 S 在 T 中出现的次数。并不是 S 的所有字符都必须在 T 中连续出现。

解决方案基于以下递归公式，对我来说这根本不直观：

假设 M(i, j) 表示 S 的 i 个字符出现在 T 的 j 个字符中的次数。基本情况：
i) 如果 j = 0 则为 0
ii) 如果 i = 0 则为 1

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

Answer 1

维基百科对它的描述非常好，这里：
“在数学、计算机科学和经济学中，动态编程是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法。它适用于表现出重叠子问题的问题-问题和最佳子结构（如下所述）。在适用时，该方法比简单方法花费的时间要少得多。

另请阅读有关重叠子问题和最佳子结构的信息。

Answer 2

也许这个链接有用：
https ://www.geeksforgeeks.org/solve-dynamic-programming-problem/ https://www.geeksforgeeks.org/tabulation-vs-memoization/
1.如何将问题分类为动态编程问题？
2. 决定状态
3. 制定状态之间的关系
4. 为状态添加记忆或制表