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

1.請找出一個不適用最佳化問題原則的例子(即表示無法使用 dynamic programming解題)。請證明你的答案。

誰會這題!!拜託教一下><

1 Answer

Rating
  • 1 decade ago
    Best Answer

    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.

Still have questions? Get your answers by asking now.