主要介绍了用Python展示动态规则法用以解决重叠子问题的一个棋盘游戏的示例,动态规划常常适用于有重叠子问题和最优子结构性质的问题,且耗时间往往远少于朴素解法,需要的朋友可以参考下

动态规划是一种用来解决定义了一个状态空间的问题的算法策略。这些问题可分解为新的子问题，子问题有自己的参数。为了解决它们，我们必须搜索这个状态空间并且在每一步作决策时进行求值。得益于这类问题会有大量相同的状态的这个事实，这种技术不会在解决重叠的子问题上浪费时间。 正如我们看到的，它也会导致大量地使用递归，这通常会很有趣。 为了说明这种算法策略，我会用一个很好玩的问题来作为例子，这个问题是我最近参加的 一个编程竞赛中的 Tuenti Challenge #4 中的第 14 个挑战问题。 Train