漫畫:什麼是動態規劃?
————————————
題目:
有一座高度是10級台階的樓梯,從下往上走,每跨一步只能向上1級或者2級台階。要求用程序來求出一共有多少種走法。
比如,每次走1級台階,一共走10步,這是其中一種走法。我們可以簡寫成 1,1,1,1,1,1,1,1,1,1。
再比如,每次走2級台階,一共走5步,這是另一種走法。我們可以簡寫成 2,2,2,2,2。
當然,除此之外,還有很多很多種走法。
————————————
第一種情況:
第二種情況:
把思路畫出來,就是這樣子:
F(1) = 1;
F(2) = 2;
F(n) = F(n-1)+F(n-2)(n>=3)
方法一:遞歸求解
由於代碼比較簡單,這裡就不做過多解釋了。
如圖所示,相同的顏色代表了方法被傳入相同的參數。
方法二:備忘錄演算法
在以上代碼中,集合map是一個備忘錄。當每次需要計算F(N)的時候,會首先從map中尋找匹配元素。如果map中存在,就直接返回結果,如果map中不存在,就計算出結果,存入備忘錄中。
方法三:動態規劃求解
程序從 i=3 開始迭代,一直到 i=n 結束。每一次迭代,都會計算出多一級台階的走法數量。迭代過程中只需保留兩個臨時變數a和b,分別代表了上一次和上上次迭代的結果。 為了便於理解,我引入了temp變數。temp代表了當前迭代的結果值。
題目二: 國王和金礦
有一個國家發現了5座金礦,每座金礦的黃金儲量不同,需要參與挖掘的工人數也不同。參與挖礦工人的總數是10人。每座金礦要麼全挖,要麼不挖,不能派出一半人挖取一半金礦。要求用程序求解出,要想得到儘可能多的黃金,應該選擇挖取哪幾座金礦?
方法一:排列組合
每一座金礦都有挖與不挖兩種選擇,如果有N座金礦,排列組合起來就有2^N種選擇。對所有可能性做遍歷,排除那些使用工人數超過10的選擇,在剩下的選擇里找出獲得金幣數最多的選擇。
代碼比較簡單就不展示了,時間複雜度也很明顯,就是O(2^N)。
F(n,w) = 0 (n
F(n,w) = g[0] (n==1, w>=p[0]);
F(n,w) =F(n-1,w) (n>1, w
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w>=p[n-1])
其中第三條是補充上去的,原因不難理解。
方法二:簡單遞歸
把狀態轉移方程式翻譯成遞歸程序,遞歸的結束的條件就是方程式當中的邊界。因為每個狀態有兩個最優子結構,所以遞歸的執行流程類似於一顆高度為N的二叉樹。
方法的時間複雜度是O(2^N)。
方法三:備忘錄演算法
在簡單遞歸的基礎上增加一個HashMap備忘錄,用來存儲中間結果。HashMap的Key是一個包含金礦數N和工人數W的對象,Value是最優選擇獲得的黃金數。
方法的時間複雜度和空間複雜度相同,都等同於備忘錄中不同Key的數量。
方法四:動態規劃
方法利用兩層迭代,來逐步推導出最終結果。在外層的每一次迭代,也就是對表格每一行的迭代過程中,都會保留上一行的結果數組 preResults,並循環計算當前行的結果數組results。
方法的時間複雜度是 O(n * w),空間複雜度是(w)。需要注意的是,當金礦只有5座的時候,動態規劃的性能優勢還沒有體現出來。當金礦有10座,甚至更多的時候,動態規劃就明顯具備了優勢。
—————END—————
點擊展開全文
※學習編程的四兄弟
※Web前端知識體系精簡
※當一名黑客應該學什麼?來看看安全工程師技能表
※深度學習大神!原百度首席科學家吳恩達宣布將創業:繼續發展人工智慧
※微軟驚呆!32TB的Win10源碼泄露?
TAG:程序猿 |
※漫畫新形態:動態漫畫
※搞笑動態圖片:逗比可愛幽默的漫畫系列動態圖片
※動態漫畫,懶人的福音
※相機的動態範圍是指什麼?
※搞笑動態圖:動物篇
※法國油畫:生活動態和場景畫得真好!
※一組能讓你把速寫畫好的動態資料!
※《失業魔王》動態漫畫來啦!
※為什麼你需要一份物聯網全景動態圖譜?
※你手機里有哪些搞笑的動態圖?
※看動畫輕鬆理解「遞歸」與「動態規劃」
※一組動態花卉插畫 ????
※搞笑動態GIF:吊打奧特曼?這是什麼操作
※動態血糖的控制標準是什麼?
※幽默搞笑的動態圖片
※一場動態漫畫概念的顛覆運動
※動態規劃:二項式序列
※奇幻的動態刺繡你見過沒?
※超贊的動態版式設計,動態版式視覺會成為一種新潮流嗎?
※一組動態圖片 有意思!