为什么插入排序不是动态编程

Question

动态规划问题具有最优的子结构，并且有一个可以用递归关系描述的解决方案。

排序列表是将元素添加到已排序的列表中，因此插入排序因此具有最佳子结构。递归关系可以描述为

Sorted_List_n = Sorted_list_n-1 + next element 

那么，为什么插入排序不考虑动态编程算法呢？我理解它是如何应用于斐波纳契数字和编辑距离的，但并不是真的超越了这一点。

Answer 1

如果问题具有以下两个属性，则可以使用动态规划（DP）解决给定问题。

1）重叠的子问题（OSP）

2）最优子结构（OSS）

即使插入排序算法具有最佳子结构属性，它不具有重叠的子问题属性。有点详细的解释如下。

在斐波纳契数字的计算情况下，我们显然有上面提到的两个属性。 （5）计算将fib（3）作为其子问题。同时，fib（4）计算将fib（3）作为其子问题。但是fib（5）= fib（4）+ fib（3）。如果我们用DP技术盲目计算fib（5），我们最终计算fib（3）两次（一个用于fib（4），另一个用于fib（3）本身）。这里，重叠的子问题之一是fib（3）如果我们可以最优地计算fib（4）和fib（3）的解，那么fib（5） ）以及可以最佳地计算。因为fib（5）只是fib（4）和fib（3）的总和。

现在，让我们试着检查这两个属性是否存在于插入排序中。 让我们说你正在排序一组数字{5,2,3,1}。

OSP：根据你所想子问题将是如下复发..

• {5，2，3，1}

• {5,2， 3}

• {5,2}

• {5}

如果仔细观察，我们可以看到没有两个相似的子问题。这意味着重叠的子问题属性不存在。如果我们可以优化地对一个大小为（n-1）的数组进行排序，那么我们也可以最优地对大小为n的数组进行排序。因此存在最佳的子结构属性。

总之，插入排序算法没有重叠的子问题属性。因此它不是DP解决方案。