轉載請標明地址或者附上我的博客地址https://georgedage.blog.csdn.net/

前言

最近接了一個項目，有關動態規劃，客戶提到，動態規劃能和spark結合在一起嗎？看來或許他對動態規劃不是很熟悉，當然，我也不能說自己對其了如指掌，但是我們熟知，當我們說起動態規劃的時候，往往是說的動態規劃算法。既然是算法，那么它是可以運用到我們的程序中的，當然，前提業務需要，系統需要。

什么是動態規劃？

在百度百科中，是這樣解釋動態規劃的：

動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優化問題時，提出了著名的最優化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動態規劃。1957年出版了他的名著《Dynamic Programming》，這是該領域的第一本著作。

好像聽起來是有點繁瑣，當然要這樣，這樣你就覺得他是比較高大上的了，就像最近《安家》電視劇中所說的——折衷主義，其實不就是混搭嗎？那么我們在這高大上的概念中，怎么去理解它呢？

也就是說它的核心問題在哪？關鍵是什么？

其實坦白來說，動態規劃問題的一般形式就是求最值。上面說到動態規劃其實是運籌學的一種最優化方法，只不過在計算機問題上應用比較多，比如說讓你求最長遞增子序列呀，最小編輯距離呀等等。

既然是要求最值，核心問題是什么呢？求解動態規劃的核心問題是窮舉。因為要求最值，肯定要把所有可行的答案窮舉出來，然后在其中找最值。

在百度百科對動態規劃的概念意義中，一句話吸引了我，是這樣說的：動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不像搜索或數值計算那樣，具有一個標準的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題，由于各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態規劃算法進行分析、討論，逐漸學會并掌握這一設計方法。

這也就是我起這個標題的原因，DP實際意義上說是一個方法，并非一個算法！！

所以說當我們設計程序的時候，特別對于數據進行分析的時候，我們難免的會有求topN的請求，數據量小還好，當數據量大的時候，我們是不是要考慮到運用一些設計方法，一些算法，或者對系統進行調優。映射到我們設計的軟件也是如此，當一個系統不斷地增加功能，不斷地有用戶的涌進時，是不是要對系統進行優化，或者為了系統的 后期維護和整體代碼的復用性，我們是不是要在編寫系統的時候運用到一些設計模式。道理是相通的！

當然說這么點，有點針對前言的一個解釋。下面以一些簡潔的話語對DP進行解釋：假設你正在使用適當的輸入數據進行一些計算。你在每個實例中都進行了一些計算，以便得到一些結果。當你提供相同的輸入時，你不知道會有相同的輸出。這就像你在重新計算之前已經計算好的特定結果一樣。那么問題出在哪里呢？你之前計算某些結果的寶貴時間被浪費掉了。你可以通過保存之前的計算結果去輕易地解決這個問題。比如通過使用恰當的數據結構。舉個例子，你可以將輸入輸出作為鍵值對映射保存起來。現在通過分析這個問題，我們可以將新的輸入（或者不在數據結構中的輸入）與其對應的輸出存儲下來。或者在字典中查找輸入并返回相應的輸出結果。這樣當你在進行一些計算時，你可以檢查數據結構中是否存在該輸入，如果數據輸入存在的話就可以直接獲得結果。我們將與這種方法相關的技巧稱作動態規劃。

一句話解釋就是：我們可以說動態規劃主要用來解決一些希望找到問題最優解的優化問題。

網上有不少運用動態規劃的算法介紹，這里就不過多敘述。希望本篇讓你對這個高大上的DP有認識上的一點見解。后期有空再更關于DP的運用！

參考：
https://baijiahao.baidu.com/s?id=1635388976060265522&wfr=spider&for=pc
百度百科

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的浅谈一下这个所谓的特殊算法——动态规划？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。