动态编程

动态编程是对 Brute Force 的改进，请参阅此示例以了解如何从 Brute Force 获得动态编程解决方案。

动态编程解决方案有两个主要要求：

1. 重叠的问题

2. 最优子结构

重叠子问题意味着问题的较小版本的结果被重复使用多次，以便得出原始问题的解决方案

最优子结构意味着有一种从子问题中计算问题的方法。

动态编程解决方案有两个主要组件，即 State 和 Transition

该国是指原问题的一个子问题。

过渡是解决问题的方法是根据它的子问题

动态编程解决方案所需的时间可以计算为 No. of States * Transition Time。因此，如果解决方案具有 N^2 状态并且转换是 O(N)，那么解决方案将花费大约时间 4。