數字三角形
描述:
?? ????? 有一個由非負整數組成的三角形，第一行只有一個數，除了最下行之外每個數的左下方和右下方各有一個數。
問題：?? ?
?? ????? 從第一行的數開始，每次可以往左下或右下走一格，直到走到最下行，把沿途經過的數全部加起來。如何走才能使得這個和盡量大？
分析：
?????? 不難看出此題是一個動態的決策問題：每次有兩種選擇——左下或右下。如果用回溯法求出所有的可能的路線，就可以從中選出最優的路線。但和往常一樣，回溯法的效率太低：一個n層數字三角形的完整路線有2^n條，當n很大時回溯法的速度將讓人無法忍受。因此本題討論用遞歸，遞推及記憶化搜索的方法實現，雖然還有其他的方法，但此時只討論學習比較相似的這幾種方法。
最先想到的是遞歸實現：
#include "stdio.h"
#define maxn 100
int a[maxn][maxn],n;inline max(int x,int y)
{return x>y?x:y;
}//遞歸計算實現
int d(int x,int y)
{return a[x][y]+(x==n?0:max(d(x+1,y),d(x+1,y+1)));
}int main()
{while(~scanf("%d",&n)) {int i,j;for(i=1;i<=n;i++){for(j=1;j<=i;j++)scanf("%d",&a[i][j]);}printf("max:%d\n",d(1,1));}return 0;
}??????? 例： 在下列計算中d(3,2)被重復調用 ?
??????????????????? d(2,1)?? 的計算會調用--> d(3,1) , d(3,2)
?? ???????????????? d(2,2) ? 的計算會調用--> d(3,2) , d(3,3)
遞推的實現：
#include "stdio.h"
#define maxn 100
int a[maxn][maxn],n;inline max(int x,int y)
{return x>y?x:y;
}//遞推實現
int d(int x,int y)
{int d[n][n],i,j; for(j=1;j<=n;j++) d[n][j]=a[n][j];for(i=n-1;i>=1;i--){for(j=1;j<=i;j++)d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);}return d[x][y];
} int main()
{while(~scanf("%d",&n)) {int i,j;for(i=1;i<=n;i++){for(j=1;j<=i;j++)scanf("%d",&a[i][j]);} printf("max:%d\n",d(1,1)); }return 0;
}
記憶化搜索實現：
#include "stdio.h"
#include "string.h"
#define maxn 100
int a[maxn][maxn],n;
int d[maxn][maxn]; //記憶化搜索所使用的狀態記憶數組
inline max(int x,int y)
{return x>y?x:y;
}/*記憶話搜索。程序分成兩部分。首先 memset(d,-1,sizeof(d)); 把d全部初始化為-1，
然后編寫遞歸函數：
*/
int distance(int i,int j)
{if(d[i][j]>=0) return d[i][j];return d[i][j]=a[i][j]+(i==n?0:max(distance(i+1,j),distance(i+1,j+1)));
}
/*上述程序依然是遞歸的，但同時也把計算結果保存在數組d中。題目中說各個數都是非負的，因此
如果已經計算過某個d[i][j]，則它應是非負的，這樣，只需把所有d初始化為-1，即可通過判斷是否
d[i][j]>=0得知是否已經被計算過。
*/ int main()
{while(~scanf("%d",&n)) {int i,j;for(i=1;i<=n;i++){for(j=1;j<=i;j++)scanf("%d",&a[i][j]);}memset(d,-1,sizeof(d)); //狀態記憶化數組初始化 printf("max:%d\n",distance(1,1)); }return 0;
}
)
)
