algorithm - Why is insertion sort not dynamic programming -

A dynamic programming problem has the optimal infrastructure and can be described by a recursive connection.

A sorted list combines an element in the previously sorted list, so the optimal basis in the entry sort can be described as a recurrence relationship

 < Code> Sorted_List_n = Sorted_list_n_ 1 + Next element  

So why is not a dynamic programming algorithm sorted in the entry? I understand how this applies to fibonacci numbers and how to edit the distance, but in fact it is not.

A

1) Extra problems (OSP)

2) Optimal sub-structure (OSS)

Although the merge sort is the property of the optimal sub-structure, but sub-problems in it, the property is not overlapping. A slightly detailed explanation is as under.

< In p> Fibonacci number calculation case, we are clearly attaining the above two properties

osp: Phib (5) in the form of phab (3) in the calculation It has its subproblem at the same time, Fib (4) has its subproblem as Fib (3) in calculation but Fib (5) = Fib (4) + Fib (3). If we calculate Fib (5) with indiscriminate DP technology, then we calculate Fib (3) for two times (one for fib (4) and fib (3). Here, one of the overlapping subproblems is Fib (3)

oss: Similarly, if we better evaluate the solution of fiber (4) and fiber (3) Can be calculated better with the solution of Fib (5), because Fib (5) is only the sum of Fib (4) and Fib (3).

Now, let us try to check whether these two properties are present in the inclusion sort or not. Let us say that you are sorting an array of numbers (5, 2, 3, 1).

osp: According to the recurrence you are thinking of subproblems as

• {5, 2, 3, 1}

• {5, 2, 3}

• {5, 2}

• {5}

If we look closely, we can see that there are two similar subprilblom which are equal. This means that overlapping sub-problems are not present in the property.

oss: If we Array of size (N-1) If we can sort better, then we have an array size (n) better then the optimal sub-structure property exists.

In summary, the sub-problems in the merge sort algorithm are not overlapping. Therefore it is not a DP solution.