? ? ? ? 動態(tài)規(guī)劃最為一個比較常見的算法類型煤辨，在做算法題的時候經(jīng)常會遇到瓦戚，下面我根據(jù)我個人見解結(jié)合網(wǎng)上知識總結(jié)一下動態(tài)規(guī)劃的使用情景與一些問題解答紫谷。
背景
????????動態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個分支轿亮，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時姿搜，提出了著名的最優(yōu)化原理(principle?of optimality)寡润，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系舅柜，逐個求解梭纹，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。
使用情境
? ? ? ? 要使用動態(tài)規(guī)劃需要滿足最優(yōu)化原理和無后效性致份，并以犧牲空間復(fù)雜度的前提優(yōu)化時間復(fù)雜度变抽，選用的時候需要考量是否有更優(yōu)的算法。動態(tài)規(guī)劃往往用于優(yōu)化遞歸問題知举，例如斐波那契數(shù)列瞬沦，如果運(yùn)用遞歸的方式來求解會重復(fù)計算很多相同的子問題，利用動態(tài)規(guī)劃的思想可以減少計算量雇锡。
? ??最優(yōu)化原理
? ??????一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何僚焦，對前面的決策所形成的狀態(tài)而言锰提，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的立肘。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)边坤。
? ? 無后效性
? ??????將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)谅年，它以前各階段的狀態(tài)無法直接影響它未來的決策茧痒，而只能通過當(dāng)前的這個狀態(tài)。換句話說融蹂，每個狀態(tài)都是過去歷史的一個完整總結(jié)旺订。這就是無后向性，又稱為無后效性超燃。
例子一区拳、最長回文子串
? ? ? ? 題目：給定一個字符串?s，找到?s?中最長的回文子串意乓。你可以假設(shè)s?的最大長度為 1000樱调。
? ? ? ? 解題思路：首先要思考：怎樣的字串滿足回文子串。若是單一一個字符届良，它是滿足回文子串定義的笆凌；當(dāng)大于等于兩個字符形成回文子串則要求從中間往兩側(cè)滿足字符逐個相等。所以一個字串要想是回文字串士葫，則要除去兩側(cè)乞而，原來內(nèi)部滿足回文字串的同時，還要滿足左右兩個字符相等为障，即P(i,j)=P(i+1,j?1)∧(Si?==Sj?)晦闰。然后只要比較當(dāng)前操作子串與最長回文子串并選取較長者即可。
? ? ? ? 代碼及步驟：
????????圖解：
例子二鳍怨、最長子序和
? ? ? ? 題目：給定一個整數(shù)數(shù)組?nums?呻右，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和鞋喇。
? ? ? ? 解題思路：該題要求求取最長的子序和声滥，可以用這樣的角度進(jìn)行思考：在遍歷到某個元素時進(jìn)行判斷，判斷前面最優(yōu)子序加上這個元素的和更大還是單這個元素更大些侦香，該元素更大則舍棄原來子序落塑，若加上前面的子序更大，則子序加上該元素作為下一個遍歷元素的前子序再進(jìn)行判斷罐韩。結(jié)束后取最大子序和即可憾赁。
? ??????代碼及步驟：
????????圖解
例子三、零錢兌換
? ? ? ? 題目：給定不同面額的硬幣 coins 和一個總金額 amount散吵。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)龙考。如果沒有任何一種硬幣組合能組成總金額蟆肆，返回?-1。你可以認(rèn)為每種硬幣的數(shù)量是無限的晦款。
? ? ? ? 解題思路：取最后一枚硬幣之前的最優(yōu)解加一的最小值即為當(dāng)前最優(yōu)解炎功，如coins=[1,3,5]，amount=6缓溅，則判斷amount=6-1或6-3或6-5的最優(yōu)解加一即為amount=6的最優(yōu)解蛇损。
? ? ? ? 代碼及步驟：
????????圖解：
總結(jié)
? ? ? ? 可以看出，動態(tài)規(guī)劃基本上都是在確定的歷史上進(jìn)行延續(xù)操作坛怪，這些歷史會被取出來存放在額外空間數(shù)組內(nèi)淤齐。動態(tài)規(guī)劃的核心還是求取最優(yōu)的理念，當(dāng)遇到求最大酝陈，最長床玻，最少之類的問題時就可以考慮一下使用動態(tài)規(guī)劃，簡單模擬一下情景沉帮，畫個圖锈死，思路理清后代碼編寫就不困難了。
