1.矩陣連乘問題：
問題描述：
矩陣連乘問題是通過給矩陣連乘時加括號，使得總的計算量最小，
問題分析：
狀態轉移方程：
再根據狀態轉移方程進行填表，右上角即為所求值，
例如，連乘矩陣個數為6，維數分別為：
填表方式如下圖所示：
2.最長公共子序列問題：
問題描述： 最長公共子序列，英文縮寫為LCS(Longest Common Subsequence)，其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列，
狀態轉移方程：
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位相同時為"1"，否則為"0"，
例如求ABCBDAB和BDCABA的LCS
灰色且帶↖箭頭的部分即為所有的LCS的字符
3.最大子段和問題：
題目描述：
給出一段序列，選出其中連續且非空的一段使得這段和最大，
轉移方程：dp[i] = max(0, dp[i - 1]) + a[i];
分析：如果說dp[i - 1]小于0，具體些就是以a[i - 1]這個數為結尾的最大子段和小于0的話，那么還不如說就不要前面的數，只留下一個a[i]呢，反之，若dp[i - 1]大于0，那么就讓dp[i] = dp[i - 1] + num[i]，這樣可以更大些，最后取值為max{dp[i]}
4.凸多邊形最優三角剖分：
題目描述：
用多邊形頂點的逆時針序串列示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形，
給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權函式w，要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權之和為最小，
解題思路：
若凸(n+1)邊形P={v0,v1,…,vn-1}的最優三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權為3個部分權的和：三角形v0vkvn的權，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權之和，可以斷言，由T所確定的這2個子多邊形的三角剖分也是最優的，因為若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權的三角剖分將導致T不是最優三角剖分的矛盾，
那么我們定義一個t[i][j]，1<=i<=j<=N,為凸子多邊形{vi-1,vi,…,vj}的最優三角剖分所對應的權函式值，即其最優值，據此定義，要計算的凸(n+1)邊形P的最優權值為t[1][n]，
t[i][j]的值可以利用最優子結構性質遞回地計算，當j-i≥1時，凸子多邊形至少有3個頂點，由最優子結構性質，t[i][j]的值應為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權值，其中i≤k≤j-1，由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使t[i][j]值達到最小的位置，由此，t[i][j]可遞回地定義為：
對于要求的t[1][n]，可以用通過由下至上的，從鏈長（多邊形的邊）為2開始計算，每次求t[i][j]的最小值，并且記錄最小值所對應的K值，根據最優子結構的性質，逐步向上就可以求出t[1][n]的最小值，
類似的，求三角劃分頂點的乘積的最小值問題，也是一樣的，
5.多邊形游戲
給定N個頂點的多邊形，每個頂點標有一個整數，每條邊上標有+(加)或是×(乘)號，并且N條邊按照順時針依次編號為1~N，
游戲規則 ：(1) 首先，移走一條邊， (2) 然后進行下面的操作： 選中一條邊E，該邊有兩個相鄰的頂點，不妨稱為V1和V2，對V1和V2頂點所標的整數按照E上所標運算子號(+或是×)進行運算，得到一個整數；用該整數標注一個新頂點，該頂點代替V1和V2 ， 持續進行此操作，直到最后沒有邊存在，即只剩下一個頂點，該頂點的整數稱為此次游戲的得分(Score)，
2、問題分析：
解決該問題可用動態規劃中的最優子結構性質來解，
設所給的多邊形的頂點和邊的順時針序列為op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中，op[i]表示第i條邊所對應的運算子，v[i]表示第i個頂點上的數值，i=1~n，
3.最優子結構性質
設所給的多邊形的頂點和邊的順時針序列為op[1],v[1],op[2],v[2],op[3],…,op[n],v[n] 其中，op[i]表示第i條邊所對應的運算子，v[i]表示第i個頂點上的數值，i=1~n，
在所給的多邊形中，從頂點i（1<=i<=n）開始，長度為j（鏈中有j個頂點）的順時針鏈p(i,j）可表示為v[i],op[i+1],…,v[i+j-1]，如果這條鏈的最后一次合并運算在op[i+s]處發生（1<=s<=j-1），則可在op[i+s]處將鏈分割為兩個子鏈p(i,s)和p(i+s,j-s)，
設m[i,j,0]是鏈p(i,j)合并的最小值，而m[i,j,1]是最大值，若最優合并在op[i+s]處將p(i,j)分為兩個長度小于j的子鏈的最大值和最小值均已計算出，即：
a=m[i,s,0] b=m[i,s,1] c=m[i+s,j-s,0] d=m[i+s,j-s,1]
(1) 當op[i+s]=’+’時
m[i,j,0]=a+c ；m[i,j,1]=b+d
該鏈的最優性由子鏈的最優性決定，最大值對應于子鏈的最大值，最小值對應于子鏈的最小值，
(2) 當op[i+s]=’*’時
m[i,j,0]=min{ac,ad,bc,bd} ； m[i,j,1]=max{ac,ad,bc,bd}
由于v[i]可能取負數，子鏈的最大值相乘未必能得到主鏈的最大值，但是注意到，主鏈的最大值和最小值可以由子鏈的最大最小值得到，
由于最優斷開位置s有1<=s<=j-1的j-1中情況， 初始邊界值為 m[i,1,0]=v[i] 1<=i<=n m[i,1,1]=v[i] 1<=i<=n
可以得到遞回運算式，將p(i,j)在op[i+s]處斷開的最大值記為maxf(i,j,s)，最小值記為minf(i,j,s)則：
因為多變形式封閉的，在上面的計算中，當i+s>n時，頂點i+s實際編號為(i+s)mod n，按上述遞推式計算出的m[i,n,1]記為游戲首次洗掉第i條邊后得到的最大得分，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339286.html
標籤：其他
上一篇：720-C語言實作2048游戲
下一篇：第一個小游戲“三子棋”超詳細