資料結構與演算法相關問題

Dynamic programming is used for problems that can be divided into small pieces, each one overlaps the other and each one of them will require the result from another one. Good example is Fibonacci numbers when F(n) needs F(n-1) and F(n-2).

So, if a problem can be divided into smaller pieces but each pieces are independent to each other. Thus, none of the results can be used by another. This will not be a good candidate for dynamic programming.

Example:
Given an integer X, find the largest prime P and P < X.

You can divide this up to smaller pieces (partitioning X) but none of the pieces will give you optimal structure and none of them will give any results that can be use to evolve to a best solution.