动态规划
与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解）
例： 背包问题之动态规划解决
问题描述：
现在有一个背包可以装4磅物品，现在要从商城里拿尽可能价值高的物品装进包里。
商城物品情况如下
每个动态规划都从一个网格（如下）开始
现在一行一行地填充该网格。
每个格子的计算公式：
填充吉他行 目前最大价值1500（吉他）
填充音箱：目前最大价值3000（音箱）
填充笔记本：目前最大价值3500（吉他+笔记本）
动态规划的原则就是将大问题拆解成多个小问题，先把小问题的最优解求出，再在考虑小问题最优解的前提下，得出最终问题的最优解
本例的背包问题中，先求出只有吉他一种物品时的最优解，再逐步添加物品，最终求出最优解
关于网格计算公式的补充：
整个动态规划求解过程中，是从小问题层逐步求解到大问题，自然每个格子要考虑的第一点就是前一格子的最大值，又，新的一层添加了新物品，所有也要考虑新物品的价值+剩余可用磅数的最大价值（上一层求得）
背包问题补充：
若再添加一个物品 ——项链{‘价值’：1000$，‘重量’：0.5磅}
此时如果沿用之前的网格
如果要装的物品为燕麦，木豆，大米 这种可以一部分一部分取出的物品
动态规划则解决不了这种情形，贪心可以。
旅游行程问题
当然我们可以用动态规划的网格法来得到一条最有价值的旅游路线
如果加入以下景点
在去巴黎的景点所花费的时间中，有0.5天是从伦敦前往巴黎的时间。
因此如果先去了埃菲尔铁塔,则去巴黎的剩下两个景点的花费时间也要减少2个小时
这种情况就不能使用之前的动态规划算法。
动态算法处理的每个子问题都是离散的
再来看一个案例
假如你要经营一个网站，网站主要任务是：英文单词翻译。即用户输入英文单词，你给出相应的翻译。 例用户输入fish，网站输出鱼
如果用户输入的hish，但词典中并没有该单词，此时应给出相似词。
怎么样才算是相似词呢？判断最大子串长度？
利用动态规划求出两字符串（fish和hish）的最大字串长度
动态规划解决问题总是要先知道网格中的各个元素：
两个坐标轴是什么？网格中的值是什么（通常为要 优化的指标 ）
1，分解问题：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）。考虑两个坐标轴为两个单词，则网格中的值为最大子串的长度。
接下来填充该网格。不断验证得到单元格公式：
单元格公式解释：
1）两字母相同，则局部最大字串要延长，即斜上方（cell[i][j]）的值加一(这里指标值在斜方向上累加)
2）若是不同，则局部最大字串为0
两字符串的最大字串长度即为网格中的最大值3。
如果用户输入fosh，那么要返回fish还是fort呢？
如果判断依据为最大子串，则会返回fort，但实际上fish和fosh更像！
因此我们考虑判断依据为两字符串的最大公共子序列长度（即两字符串公共字符的个数）
求最大公共子序列的单元格公式为：
fosh和fort的最大公共子序列长度为2
fosh和fish的最大公共子序列长度为3
此时就可以返回正确结果fish而非fort。
1，动态规划通常用于解决 在给定约束条件下优化某个指标值
2，动态规划的原则就是：将大问题分解成小问题，在解决了小问题的条件下，逐步求解大问题。（一个分解问题的方法就是，将条件逐渐减少，从最简单的情况开始分析）
3，动态规划使用的一个必要条件为： 分解出来的每个小问题都是离散的
4，每种动态规划方案都设计网格
4.1，网格的每个格子都是一个小问题
4.2，网格的每个格子的值都是指标的值
4.3，单元格计算公式需要 具体问题具体分析 。
绛旓細鍔ㄦ佽鍒涓庡叾瀹冪畻娉曠浉姣旓紝澶уぇ鍑忓皯浜嗚绠楅噺锛屼赴瀵屼簡璁＄畻缁撴灉锛屼笉浠呮眰鍑轰簡褰撳墠鐘舵佸埌鐩爣鐘舵佺殑鏈浼樺硷紝鑰屼笖鍚屾椂姹傚嚭浜嗗埌涓棿鐘舵佺殑鏈浼樺硷紝杩欏浜庡緢澶氬疄闄呴棶棰樻潵璇存槸寰堟湁鐢ㄧ殑銆傚姩鎬佽鍒掔浉姣斾竴鑸畻娉曚篃瀛樺湪涓瀹氱己鐐癸細绌洪棿鍗犳嵁杩囧锛屼絾瀵逛簬绌洪棿闇姹傞噺涓嶅ぇ鐨勯鐩潵璇达紝鍔ㄦ佽鍒掓棤鐤戞槸鏈浣虫柟娉曪紒鍔ㄦ佽鍒掔畻娉...
绛旓細1.闃舵 闃舵鏄寚鐮旂┒鐨勪簨鐗╁湪鍙戝睍杩囩▼涓墍澶勭殑鏃舵鎴栧湴娈点傚鐞嗗闃舵鍐崇瓥闂锛岄渶瑕佸皢鍏ㄨ繃绋嬪垝鍒嗚嫢骞查樁娈碉紝姣忎釜闃舵杩涜涓娆℃妷鎷┿傝嫢婕斿彉杩囩▼鏄鏁ｇ殑锛屽垯鐢ㄥ簭鍒楃紪鍙穒=1锛2锛屸︼紝n琛ㄧず锛岀О涓洪樁娈靛彉閲忋傚畠鍙互鏄┖闂达紝涔熷彲浠ユ槸鏃堕棿銆傝嫢涓烘椂闂达紝鍒欐寜鐩哥瓑澧為噺螖t绂绘暎锛屾垨鎸夎繛缁彉鍖栵紝浠ュ彉閲弔琛ㄧず銆2....
绛旓細鍔ㄦ佽鍒鎬濇兂鍜岄掑綊鎬濇兂閮芥槸绠楁硶璁捐涓父鐢ㄧ殑鎬濇兂锛屽畠浠箣闂存湁璁稿鐩镐技涔嬪锛屼絾涔熷瓨鍦ㄤ竴浜涗笉鍚屼箣澶勩傚姩鎬佽鍒掓槸涓绉嶈嚜搴曞悜涓婄殑绠楁硶璁捐鏂规硶锛屽畠閫氬父鐢ㄤ簬姹傝В鍏锋湁鏈浼樺瓙缁撴瀯鎬ц川鐨勯棶棰樸傚姩鎬佽鍒掗氬父闇瑕佷娇鐢ㄩ掑綊鏉ュ疄鐜帮紝浣嗗畠浠箣闂寸殑涓昏鍖哄埆鍦ㄤ簬鍔ㄦ佽鍒掍細灏嗛棶棰樼殑瑙ｅ瓨鍌ㄥ湪涓涓〃鏍间腑锛岃屼笉鏄瘡娆￠兘閲嶆柊璁＄畻...
绛旓細璐濆皵鏇肩瓑鎵鎻愬嚭鐨鍔ㄦ佽鍒鏈浼樺寲鍘熺悊鏄細鈥滀竴涓繃绋嬬殑鏈浼樼瓥鐣ュ叿鏈夎繖鏍风殑鎬ц川锛屽嵆鏃犺鍒濆鐘舵佸拰鍒濆鍐崇瓥濡備綍锛屼粠杩欎竴鍐崇瓥鎵瀵艰嚧鐨勬柊鐘舵佸紑濮嬶紝浠ュ悗鐨勪竴绯诲垪鍐崇瓥蹇呴』鏄渶浼樼殑鈥濄傚鍓嶆墍杩帮紝鍔ㄦ佽鍒掗嗗簭鍐崇瓥杩囩▼涓紝鎬绘槸浠庢暣涓繃绋嬬殑缁堢寮濮嬭绠楋紝鍚戝绔愰樁娈垫嫨浼橈紝鍏朵腑姣忎竴涓樁娈甸兘瑕佽冭檻鏈潵鍚勯樁娈...
绛旓細鍔ㄦ佽鍒鏄敤鏉ユ眰瑙ｆ渶浼樺寲闂鐨勪竴绉嶆柟娉曘傚父瑙勭畻娉曚功涓婂己璋冪殑鏄棤鍚庢晥鎬у拰鏈浼樺瓙缁撴瀯鎻忚堪锛岃繖濂楃悊璁烘槸姝ｇ‘鐨勶紝浣嗘槸閫傜敤涓庡惁涓庝綘鐨勭姸鎬佽〃杩版湁鍏炽傝嚦浜庡垝鍒嗛樁娈典粈涔堢殑灏辨湁浜涙壇娣′簡锛氬姩鎬佽鍒掍笉涓瀹氭湁鎵璋撶殑闃舵銆傚叾瀹炶川鏄姸鎬佺┖闂寸殑鐘舵佽浆绉汇備笅闈㈢殑鐞嗚В涓烘垜涓汉鍗佸勾绔炶禌涔嬫荤粨銆傚熀鏈笂鍦╫i鍜宎cm涓垜娌℃湁...
绛旓細鍔ㄦ佽鍒鐨勫熀鏈楠ゆ槸鍒掑垎闃舵鍜岄夋嫨鐘舵併佺‘瀹氬喅绛栧苟鍐欏嚭鐘舵佽浆绉绘柟绋嬪拰鍐欏嚭瑙勫垝鏂圭▼锛堝寘鎷竟鐣屾潯浠讹級銆1銆佸垝鍒嗛樁娈靛拰閫夋嫨鐘舵侊細鎸夌収闂鐨勬椂闂存垨绌洪棿鐗瑰緛锛屾妸闂鍒嗕负鑻ュ共涓樁娈点傛敞鎰忚繖鑻ュ共涓樁娈典竴瀹氳鏄湁搴忕殑鎴栬呮槸鍙帓搴忕殑锛堝嵆鏃犲悗鍚戞э級锛屽惁鍒欓棶棰樺氨鏃犳硶鐢ㄥ姩鎬佽鍒掓眰瑙ｃ傚皢闂鍙戝睍鍒板悇涓樁娈垫椂鎵...
绛旓細鍔ㄦ佽鍒绠楁硶 姒傚康鍙婃剰涔 鍔ㄦ佽鍒(dynamic programming)鏄繍绛瑰鐨勪竴涓垎鏀,鏄眰瑙ｅ喅绛栬繃绋(decision process)鏈浼樺寲鐨勬暟瀛︽柟娉曘20涓栫邯50骞翠唬鍒濈編鍥芥暟瀛﹀R.E.Bellman绛変汉鍦ㄧ爺绌跺闃舵鍐崇瓥杩囩▼(multistep decision process)鐨勪紭鍖栭棶棰樻椂,鎻愬嚭浜嗚憲鍚嶇殑鏈浼樺寲鍘熺悊(principle of optimality),鎶婂闃舵杩囩▼杞寲涓轰竴绯诲垪鍗曢樁娈...
绛旓細鍔ㄦ佽鍒鐨勯掓帹鍏崇郴寮忔湁閫嗗簭閫掓帹鍜岄『搴忛掓帹涓ょ褰㈠紡銆傞嗗簭閫掓帹姹傝В杩囩▼鏄牴鎹竟鐣屾潯浠朵粠k=n寮濮嬶紝鐢卞悗鍚戝墠閫嗘帹锛屽彲閫愭姹傚緱鍚勬鐨勬渶浼樺喅绛栧拰鐩稿簲鐨勬渶浼樺硷紝褰撴渶鍚庢眰鍑篺1锛坸1锛夋椂锛屼究寰楀埌鏁翠釜闂鐨勬渶浼樿В銆傞『搴忛掓帹姹傝В杩囩▼鏄牴鎹竟鐣屾潯浠朵粠k=1寮濮嬶紝鐢卞墠鍚戝悗椤烘帹锛屽彲閫愭姹傚緱鍚勬鐨勬渶浼樺喅绛栧拰...
绛旓細鍔ㄦ佽鍒娉昜dynamic programming method (DP)]鏄郴缁熷垎鏋愪腑涓绉嶅父鐢ㄧ殑鏂规硶銆傚湪姘磋祫婧愯鍒掍腑,寰寰娑夊強鍒板湴琛ㄦ按搴撹皟搴︺佹按璧勬簮閲忕殑鍚堢悊鍒嗛厤銆佷紭鍖栬皟搴︾瓑闂,鑰岃繖浜涢棶棰樺張鍙鍖栦负澶氶樁娈靛喅绛栬繃绋嬮棶棰樸傚姩鎬佽鍒掓硶鏄В鍐虫绫婚棶棰樼殑鏈夋晥鏂规硶銆傚姩鎬佽鍒掓硶鏄20涓栫邯50骞翠唬鐢辫礉灏旀浖锛圧. Bellman锛夌瓑浜烘彁鍑,鐢ㄦ潵瑙ｅ喅...
绛旓細鍔ㄦ佽鍒鍙皢涓涓椿鍔ㄨ繃绋嬪垎鎴愯嫢骞蹭釜浜掔浉鑱旂郴鐨勯樁娈碉紝鍦ㄥ畠鐨勬瘡涓闃舵閮介渶瑕佷綔鍑哄喅绛栵紝浠庤屼娇鏁翠釜杩囩▼杈惧埌鏈濂界殑娲诲姩鏁堟灉銆傚綋鐒讹紝鍚勪釜闃舵鍐崇瓥鐨勯夊彇涓嶆槸浠绘剰纭畾鐨勶紝瀹冧緷璧栦簬褰撳墠闈复鐨勭姸鎬侊紝鍙堝奖鍝嶄互鍚庣殑鍙戝睍锛屽綋鍚勪釜闃舵鍐崇瓥纭畾鍚庯紝灏辩粍鎴愪竴涓喅绛栧簭鍒楋紝鍥犺屼篃灏辩‘瀹氫簡鏁翠釜杩囩▼鐨勪竴鏉℃椿鍔ㄨ矾绾裤傚湪寰楀埌鏈鍚...
