文章目錄

• 前言
• 動態規劃的套路
• BM62 斐波那契數列
• • 1. 遞歸暴力求解
  • 2. 子問題優化的遞歸求解
• 耗時比較

前言

《華為機試真題》專欄含牛客網華為專欄、華為面經試題、華為OD機試真題。

如果您在准備華為的面試，期間有想了解的可以私信我，我會盡可能幫您解答，也可以給您一些建議！

本文解法非最優解（即非性能最優）。

動態規劃的套路

動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策過程最優化的過程。

動態規劃的題目比較多，比如：最長遞增子序列問題、最短路徑問題、背包問題、資源分配問題等。

動態規劃並不是萬能的，適用動態規劃的問題必須滿足最優子結構和無後效性。

• 最優子結構：動態規劃問題一定會具備最優子結構，通過子問題的最值得到原問題的最值。
• 無後效性：將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態࿰