一、實驗目的 2
二、實驗內容 2
2.1數塔問題 2
2.2 最長單調遞增子串行問題 2
三．演算法設計 2
3.1 數塔問題 2
3.1.1演算法描述 2
3.1.2 函式設計 3
3.2 最長單調遞增子串行問題 3
3.1.1演算法描述 3
3.1.2 函式設計 3
四.程式除錯及執行結果分析 4
4.1數塔問題 4
4.2最長單調遞增子串行問題 4
五.實驗總結 4
六．附錄 5
6.1數塔問題 5
6.2最長單調遞增子串行問題 5
1．掌握動態規劃演算法的基本思想，包括最優子結構性質和基於**的最優值計算方法。
2．熟練掌握分階段的和遞推的最優子結構分析方法。
3．學會利用動態規劃演算法解決實際問題。
給定乙個數塔，其儲存形式為如下所示的下三角矩陣。在此數塔中，從頂部出發，在每一節點可以選擇向下走還是向右走，一直走到底層。請找出一條路徑，使路徑上的數值和最大。
設計乙個o（n2）複雜度的演算法，找出由n個數組成的序列的最長單調遞增子串行。
從頂點出發時到底向左走還是向右走應取決於是從左走能取到最大值還是從右走能取到最大值：
1.只要左右兩道路徑上的最大值求出來了才能作出決策。
2.同樣的道理下一層的走向又要取決於再下一層上的最大值是否已經求出才能決策。
3.這樣一層一層推下去，直到倒數第二層時就非常明了。
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)
if(a[i+1][j][1]>a[i+1][j+1][1])
a[i][j][1]=a[i][j][1]+a[i+1][j][1];
a[i][j][2]=0;}else }
動態規劃程式設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊演算法。不像搜尋或數值計算那樣，具有乙個標準的數學表示式和明確清晰的解題方法。動態規劃給了我一種新的思考方式，讓我不再侷限於點之間。
除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。動態規劃是一種很好的解題方法。
for (int i = 0; i < n; i++)
}判斷並找出最大和
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)}}
for (int i = 0; i < n; i++)
a[i]= b[i]=1; c[i]=0; }
for(int i=n-2;i>=0;i--)
max=0;p=0; for(int j=i+1;jif(a[i]max)
max=b[j]; p=j;} }
if(p!=0)//存在符合條件的數時
b[i]=b[p]+1; c[i]=p; }}
max=0; p=0;
for(int i=0;iif(b[i]>max)
max=b[ip=i; }}
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...
5動態規劃演算法習題答案
1 最大子段和問題 給定整數序列，求該序列形如的子段和的最大值 1 已知乙個簡單演算法如下 int maxsum int n,int a,int best i,int bestj return sum 試分析該演算法的時間複雜性。2 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。3 試說...
揹包問題的動態規劃演算法
1.u1 c 2.m n 1時，fm u 恒為0 3.u 0時，fm u 為0 狀態轉移方程為u k 1 uk xk wk。動態規劃基本方程為 wm u時，fm u f m 1 u 否則fm u 為f m 1 u與f m 1 u wm pm中的較大者。定義 n 1 c矩陣f，其m行u列處為fm u ...