在很多问题中，动态规划算法是我们的最优选择，比起递归算法，动态规划算法的时间复杂度和空间复杂度都更加优越，可以处理的数据规模更大。但是，动态优化算法的时间复杂度为O（N*V），也就是说，当需要处理的数据规模较大时，使用动态规划算法也存在超时的可能性，因此，我们需要在动态规划的基础上做出优化。
1. 使用空间换时间：将中间结果缓存在数组中，避免重复计算。
2. 无后效性：假设问题可以分解为若干子问题，某些子问题的解可以不受其他子问题的解的影响，则可以去掉一些不必要的计算。
3. 剪枝：在搜索的过程中，利用一些条件限制最优解的范围，过滤掉不需要搜索的部分，提高性能。
4. 动态规划与贪心算法：当问题可以用贪心算法解决时，应优先使用贪心算法，它的时间复杂度要小于动态规划算法。
5. 构建最优解：利用最优子结构可以减少搜索的规模，进而提高搜索效率。
下面用一个具体的样例记录以下动态优化的过程：
题目描述：
代码段：
这段代码在题目规定的时间内完成数据的计算，得到正确的结果。
题目升级：
显然，和上面的题目相比，题干没有任何的变化，只是处理数据的规模变大了，而在处理该规模的数据时，上面的代码显示超时，也就是说，上述动态规划算法需要优化。
空间复杂度优化
上述代码将状态转移表由二维数组转换为一维数组，降低了代码对空间复杂度的要求，但是不难看出，虽然设置了一定的循环条件，代码的时间复杂度仍然是O(N*M），也就是，运行该题目仍然会超时。问题并没有解决。
两段代码均只能通过13组数据，因此，还需要在运行时间上进行优化。
时间复杂度优化
如何能够降低时间复杂度，我首先想到的是剪纸，通过一定的条件限制，比如二分法，将时间复杂度降维O(NlogM)。
代码运行结果：
通过运行结果可以看出，这种方法错误。
标记+递归法代码：
这段代码表面上看上去和普通的递归法极为相似，但是实际上却有很大的不同。
普通递归法代码：
不同之处的分析：
普通递归法：在没有if条件语句的限制下，递归的搜索空间为
。加上if语句，可以减少部分分枝，但是当背包容量较大时，if语句所起的限制作用有限，时间复杂度趋近于O()
标记+递归：二进制机制用于标记每个物品状态，放入或者未放入背包。这种情况下，递归的搜索空间被缩小为n!。时间复杂度大大减小。
实质上，这两种算法的区别就是深度优先遍历和广度优先遍历的区别。
但是，标记+递归的时间复杂度还是过高，无法通过题目要求。
二进制+动态规划：
该方法通过测试。
总结：对算法进行优化时，需要综合考虑时间和空间复杂度。
