求lcs的問題。當xi=yj時，求c[i,j]只需知道c[i-1,j-1]
而無需用到c[i,0]～c[i,j-1]及c[i-1,j]～c[i-1,n]。
∴ 當只需求出乙個lcs時，
可能有一些c[p,q]在整個求解過程中都不會用到。
一般地，當某個問題可以用動態規劃法求解,
但二維陣列中有相當一部分元素在整個計算中都不會被用到。我們就不需要以遞推方式逐個計算二維陣列中元素，
而採用備忘錄方法：陣列中的元素只是在需要計算時才去計算，
計算採用遞迴方式，值計算出來之後將其儲存起來以備它用。
lcs問題：
首先將c[i,0](0≤i≤m)與c[0,j](1≤j≤n)初始化為0。
其餘m×n個c[i,j]全部初始化為-1。
計算c[i,j]的遞迴演算法lcs_l2(x,y, i,j,c)（備忘錄方法）：
若x[i]=y[j]，則去檢查c[i-1,j-1]，若c[i-1,j-1]> -1（已經計算出來），就直接把c[i-1,j-1]+1賦給c[i,j]，返回。
若c[i-1,j-1]=-1（尚未計算出來），
就遞迴呼叫lcs_l2(x,y, i-1,j-1,c) 計算出c[i-1,j-1]，
然後再把c[i-1,j-1]+1賦給c[i,j] ，返回。
若x[i] y[j]，則要檢查c[i-1,j]和c[i,j-1]。
若兩者均 > -1（已經計算出來），
則把max 賦給c[i,j]，返回。
若c[i-1,j], c[i,j-1] 兩者中有乙個等於-1（尚未計算出來），
或兩者均等於-1，就遞迴呼叫lcs_l2將其計算出來，
然後再把max 賦給c[i,j]。
∴若有大量的子問題無需求解時，用備忘錄方法較省時。
但當無需計算的子問題只有少部分或全部都要計算時，
用遞推方法比備忘錄方法要好（如矩陣連乘，最優二分搜尋樹）。
動態規劃法解
2011級3班張思源 動態規劃演算法原理 將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解 對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來。為了不去求解相同的子問題，引入乙個陣列，把所有子問題的解存於該陣列中，這就是動態規劃所採用...
揹包問題的動態規劃法
揹包問題 在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w 2 wn，與之相對應的價值為p1,p2 pn。求出獲得最大價值的方案。注意 在本題中，所有的重量值均為整數。演算法分析 對於揹包問題，通常的處理方法是搜尋。用遞迴來完成搜尋，演算法設計如下 function make i ...
最大欄位和問題動態規劃法
淮海工學院計算機工程學院 實驗報告書 課程名 演算法分析與設計 題目 實驗2 動態規劃演算法 最大子段和問題 班級軟體081班 學號110831116 姓名陳點點 實驗2 動態規劃演算法 實驗目的和要求 1 深刻掌握動態規劃法的設計思想並能熟練運用 2 理解這樣乙個觀點 同樣的問題可以用不同的方法解...