Rumah pembangunan bahagian belakang tutorial php php算法学习之动态规划

php算法学习之动态规划

Feb 06, 2017 am 09:52 AM

 动态规划程序设计是对解最优化问题的一种途径、一种方法,最终问题的最优解可以通过前面子问题的最优解推导出来。


对于动态规划这个算法,自己学习的还不是很透彻,简单的总结自己学习的感受是:

动态规划思想中融合了递归和分治的思想,但不同于分治的是,动态规划求解中会通过状态记录求解过程中每一个分支的最优解法,以此节省了许多分支的重复计算。

动态规划最重要同样也是最难的两步是找到描述子问题的状态以及状态间的推导关系。

比较可能使用动态规划的问题:求最大最小值、是否有可行方案以及可行方案个数。

先来一个最常见的题体验一下,求斐波那契数列(不知道的同学请自行百度一下)某个位置的值?
应用分治法求解代码

863.jpg

分治求解过程中,会有许多重复的运算,如下图3和2都被重复运算了两次,index值越大重复计算的次数就越多。

864.jpg

ok,下面我们看一下动态规划如何进行优化。

865.jpg

 我们定义了一个数组来记录斐波那契每个位置的值,这就相当于我们定义了一个状态;每个位置的值等于它前面两个的加和,这就相当于一个状态转移方程。
这里通过数组记录状态就是一种以空间换时间的思想,其实和我们平时开发用到的缓存的设计很像。

总结动态规划求解可以分为4步:
1、确定要解决的子问题,即状态的定义。
2、列出状态转移方程。
3、根据给定条件,初始化已知状态值。
4、求解最终问题解。

下面再来解一道比较有意思的问题,爬楼梯:

866.jpg

以上就是php算法学习之动态规划的内容,更多相关内容请关注PHP中文网(www.php.cn)!


Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
2 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Repo: Cara menghidupkan semula rakan sepasukan
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Cara mendapatkan biji gergasi
4 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Konfigurasi Projek CakePHP Konfigurasi Projek CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan memahami Pembolehubah Persekitaran, Konfigurasi Umum, Konfigurasi Pangkalan Data dan Konfigurasi E-mel dalam CakePHP.

Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Panduan Pemasangan dan Naik Taraf PHP 8.4 untuk Ubuntu dan Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 membawa beberapa ciri baharu, peningkatan keselamatan dan peningkatan prestasi dengan jumlah penamatan dan penyingkiran ciri yang sihat. Panduan ini menerangkan cara memasang PHP 8.4 atau naik taraf kepada PHP 8.4 pada Ubuntu, Debian, atau terbitan mereka

Tarikh dan Masa CakePHP Tarikh dan Masa CakePHP Sep 10, 2024 pm 05:27 PM

Untuk bekerja dengan tarikh dan masa dalam cakephp4, kami akan menggunakan kelas FrozenTime yang tersedia.

Muat naik Fail CakePHP Muat naik Fail CakePHP Sep 10, 2024 pm 05:27 PM

Untuk mengusahakan muat naik fail, kami akan menggunakan pembantu borang. Di sini, adalah contoh untuk muat naik fail.

Penghalaan CakePHP Penghalaan CakePHP Sep 10, 2024 pm 05:25 PM

Dalam bab ini, kita akan mempelajari topik berikut yang berkaitan dengan penghalaan ?

Bincangkan CakePHP Bincangkan CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP ialah rangka kerja sumber terbuka untuk PHP. Ia bertujuan untuk menjadikan pembangunan, penggunaan dan penyelenggaraan aplikasi lebih mudah. CakePHP adalah berdasarkan seni bina seperti MVC yang berkuasa dan mudah difahami. Model, Pandangan dan Pengawal gu

Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Cara Menyediakan Kod Visual Studio (Kod VS) untuk Pembangunan PHP Dec 20, 2024 am 11:31 AM

Kod Visual Studio, juga dikenali sebagai Kod VS, ialah editor kod sumber percuma — atau persekitaran pembangunan bersepadu (IDE) — tersedia untuk semua sistem pengendalian utama. Dengan koleksi sambungan yang besar untuk banyak bahasa pengaturcaraan, Kod VS boleh menjadi c

Pengesah Mencipta CakePHP Pengesah Mencipta CakePHP Sep 10, 2024 pm 05:26 PM

Pengesah boleh dibuat dengan menambah dua baris berikut dalam pengawal.

See all articles