1、算法設計與分析實驗報告實驗名稱動態規劃學 院數學與計算機學院班級信科00000學號 6666666666姓 名 0000002016 年姓名實驗日期實驗名稱動態規劃【實驗目的】理解動態規劃算法的思想，能靈活利用動態規劃算法解決實際計算問題?！緦嶒瀮热荨繀⒖荚创a MatrixChain.cpp,RecurveMatrixChain.cpp,lookupMatrixChain.cpp閱讀參考代碼，理解動態規劃算法的主要數據結構；比較動態規劃算法和分治算法的異同；比較規劃算法和備注算法的異同；針對4.6, 4.7兩節問題，在巳有動態規劃算法基礎上，編程求解最優解;【實驗原理】（含相關算法流程圖，可寫

2、多頁）【實驗環境】微型計算機；Windows7操作系統；Code blocks、vs2012 集成開發環境?！緦嶒炦^程與結果】（附主要源碼及運行結果截圖）最長單調子序列問題#include #define MAXLENGTH 1000using namespace std;int LongestIncreasingSubsequence（int X, int n, int c, int line）（int pathMAXLENGTH;gEi岫=i;c0 = 1；輸入數組5= 1；in；+i，ci = 1;for (int j = 0; j = Xj & cj + 1 ci)ci = cj +

3、1;蛔=int max = 0;int end = -1;得到最大和獲得最長遞增子序列的最后一個元素的索引int cMAXLENGTH;int lineMAXLENGTH;while (cin n, n != 0)(for (int i = 0; i Xi;int max = LongestIncreasingSubsequence(X, n, c, line);cout Longest Increasing Subsequences Length: max = 0; -i)(cout linei;cout endl;:/打印res數組for (int i = 1; i = n; i+) (f

4、or (int j = 1; j = i; j+) (，;廣5cout endl;*/cout res11 endl;/最 大路徑和值/找出靠右路徑int y = 1;cout arr1y ;/頂部最大for (int i = 2; i = n; i+) (/從上往下找，只需要比較y和y+1,相應輸出“最大值下標對應的”原值if (resiy = resiy+1) cout arriy+1 : y = y+1;/更新 yelse ifcout endl;return 0; IXWpprQliMgtolMPebiWViCM 6 4 5re.imMl Q (QiO) 皿昌皿訪皿 tijw : 89

5、. 457 s te-F? snv key to -critLrv.H-快拘械吾滴A注全:2I41&【實驗小結】分治法與動態規劃主要共同點：二者都要求原問題具有最優子結構性質，都是將原問題分而治之,分解成若十個規模較 小（小到很容易解決的程序）的子問題.然后將子問題的解合并，形成原問題的解.分治法與動態規劃實現方法：分治法通常利用遞歸求解.動態規劃通常利用迭代法自底向上求解,但也能用具有記憶功能的遞歸法自頂向下 求解.分治法與動態規劃主要區別：分治法將分解后的子問題看成相互獨立的.動態規劃將分解后的子問題理解為相互間有聯系，有重疊部分.2.相同點解決的問題都需要最優子結構備忘錄方法與動態規劃和遞歸的區別：1、動態規劃是自低向上，備忘錄方法是自頂向下，遞歸是自頂向下2、動態