動態規劃中的無後效性是什麼意思

在動態規劃（Dynamic Programming）中，無後效性（No-Preemption）是一個關鍵性質，它指的是一旦某個子問題的狀態被確定下來，那麼這個狀態的值就只取決於其本身的定義，而不受之後的決策影響。換句話說，無後效性保證了動態規劃算法在解決子問題時，只依賴於已經做出的決策，而不會受到未來決策的影響。

舉個例子，考慮一個簡單的貨幣換算問題，我們想要找到將一筆金額換成若干種不同面值的貨幣的最小費用。假設有兩種面值的貨幣：5元和1元。如果我們有10元的目標金額，我們可以選擇換成5元的貨幣一次，或者換成1元的貨幣五次。無論我們選擇哪種方式，一旦我們已經做出了換取貨幣的決定，我們就不會再改變這個決定。這就是無後效性的體現。

無後效性是動態規劃算法能夠重用子問題解的重要條件。因為我們知道一個子問題的解只依賴於其先前的狀態，我們可以快取這些解，以便在需要時快速訪問它們，而不必重新計算。這就是動態規劃算法高效性的來源之一。