首頁 後端開發 php教程 php演算法學習之動態規劃

php演算法學習之動態規劃

Feb 06, 2017 am 09:52 AM

 動態規劃程序設計是解最佳化問題的一種途徑、一種方法,最終問題的最適解可以透過前面子問題的最適解推導出來。


對於動態規劃這個演算法,自己學習的還不是很透徹,簡單的總結自己學習的感受是:

動態規劃思想中融合了遞歸和分治的思想,但不同於分治的是,動態規劃求解中會透過狀態記錄求解過程中每一個分支的最優解法,以此節省了許多分支的重複計算。

動態規劃最重要同樣也是最難的兩步是找到描述子問題的狀態以及狀態間的推導關係。

比較可能使用動態規劃的問題:求最大值、是否有可行方案、可行方案數量。

先來一個最常見的題體驗一下,求斐波那契數列(不知道的同學請自行百度一下)某個位置的值?
應用分治法求解程式碼

php演算法學習之動態規劃

分治求解過程中,會有許多重複的運算,如下圖3和2都被重複運算了兩次,index值越大重複計算的次數就越多。

php演算法學習之動態規劃

ok,下面我們來看看動態規劃如何進行最佳化。

php演算法學習之動態規劃

 我們定義了一個陣列來記錄斐波那契每個位置的值,這就相當於我們定義了一個狀態;每個位置的值等於它前面兩個的加和,這就相當於一個狀態轉移方程式。
這裡透過陣列記錄狀態就是一種以空間換時間的思想,其實和我們平常開發用到的快取的設計很像。

總結動態規劃求解可以分為4步驟:
1、確定要解決的子問題,即狀態的定義。
2、列出狀態轉移方程式。
3、根據給定條件,初始化已知狀態值。
4、求解最終問題解。

下面再來解一道比較有趣的問題,爬樓梯:

php演算法學習之動態規劃

以上就是php演算法學習動態規劃的內容,更多相關內容請關注PHP中文網(www.php.cn)!


本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
3 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 適用於 Ubuntu 和 Debian 的 PHP 8.4 安裝和升級指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 帶來了多項新功能、安全性改進和效能改進,同時棄用和刪除了大量功能。 本指南介紹如何在 Ubuntu、Debian 或其衍生版本上安裝 PHP 8.4 或升級到 PHP 8.4

CakePHP 使用資料庫 CakePHP 使用資料庫 Sep 10, 2024 pm 05:25 PM

在 CakePHP 中使用資料庫非常容易。本章我們將了解CRUD(建立、讀取、更新、刪除)操作。

CakePHP 日期和時間 CakePHP 日期和時間 Sep 10, 2024 pm 05:27 PM

為了在 cakephp4 中處理日期和時間,我們將使用可用的 FrozenTime 類別。

CakePHP 檔案上傳 CakePHP 檔案上傳 Sep 10, 2024 pm 05:27 PM

為了進行文件上傳,我們將使用表單助理。這是文件上傳的範例。

討論 CakePHP 討論 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的開源框架。它旨在使應用程式的開發、部署和維護變得更加容易。 CakePHP 基於類似 MVC 的架構,功能強大且易於掌握。模型、視圖和控制器 gu

CakePHP 建立驗證器 CakePHP 建立驗證器 Sep 10, 2024 pm 05:26 PM

可以透過在控制器中新增以下兩行來建立驗證器。

CakePHP 日誌記錄 CakePHP 日誌記錄 Sep 10, 2024 pm 05:26 PM

登入 CakePHP 是一項非常簡單的任務。您只需使用一項功能即可。您可以記錄任何後台程序(如 cronjob)的錯誤、異常、使用者活動、使用者採取的操作。在 CakePHP 中記錄資料很容易。提供了 log() 函數

如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 如何設定 Visual Studio Code (VS Code) 進行 PHP 開發 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也稱為 VS Code,是一個免費的原始碼編輯器 - 或整合開發環境 (IDE) - 可用於所有主要作業系統。 VS Code 擁有大量針對多種程式語言的擴展,可以輕鬆編寫

See all articles