數字三角形
有正實數構成的數字三角形排列形式如圖所示，第一行的數為\(a_{11}\)；第二行的數從左到右依次為\(a_{21}\)，\(a_{22}\)；...第n行的數為\(a_{n1}\)，\(a_{n2}\)，...，\(a_{nn}\)，從\(a_{11}\)開始，每一行的數\(a_{ij}\)只有兩條邊可以分別通向下一行的兩個數\(a_{(i+1)j}\)和\(a_{(i+1)(j+1)}\)，請設計一個演算法，計算出從\(a_{11}\)通到\(a_{n1}\)，\(a_{n2}\)，...，\(a_{nn}\)中某個數的一條路徑，并使得該路徑上的數之和達到最大，
定義陣列元素
把當前的位置\((i,j)\)看成一個狀態，然后定義狀態\((i,j)\)的標記函式\(F(i,j)\)為從格子\((i,j)\)出發時能得到的最大和（包括\(F(i,j)\)本身的值）
定義狀態轉移方程
接下來，看不同狀態之間是如何轉移的，
從\((i,j)\)出發，有2種選擇，去\((i+1,j)\)或\((i+1,j+1)\)，
為了滿足題目要求，我們選擇\(F(i+1,j)\)和\(F(i+1,j+1)\)中較大的一個，
所以得到了狀態轉移方程
\(F(i,j)=a(i,j)+max{F(i+1,j),F(i+1,j+1)}\)
所以如果從第一個位置\((1,1)\)開始一直依靠這個方程取max向下走的話，就會得到最好情況，滿足優化原則，這個性質稱為最優子結構，
找出初值，最小子問題
最左邊：\(F[i,1]=F[i-1,1]+a_{i1}\) \(i=2,3,...,n\)
最右邊：\(F[i,i]=F[i-1,i-1]+a_{ii}\) \(i=2,3,...,n\)
\(F[1,1]=a_{11}\)
問題的最優路徑的和是\(max\){\(F[n,j]|j=1,2,...,n\)}
這個遞推演算法中，\(i\)是逆序列舉的，
int i,j
for(j=1;j<=n;j++)
F[n,j]=a[n,j];
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
F[i,j]=a[i,j]+max{F[i+1,j],F[i+1,j+1]};
所以演算法的時間復雜度是\(O(n^2)\)
現在得到了路徑的最大值，要得到該路徑，需設立標記函式，
定義標記函式\(k[i,j]\)，記錄得到最優\(F[i,j]\)時的路徑選擇，即
\[k[i,j] = \left\{ \begin{array}{lr} j & 若F[i-1,j]>F[i-1,j-1]\\ j-1 & 否則 \end{array} \right. \]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60086.html
標籤：其他