動态規劃——數字三角形

給定一個n行數字組成的數字三角形，計算從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。

遞歸解法

int rec_triangle(int a[][m])   //将數組作為函數參數
{
	int i,j;
	for(i=m-2;i>=0;i--)     //從倒數第二行開始計算，倒數第二行的計算是基于最後一行的， 
		for(j=0;j<=i;j++)
		//倒數第二行的每個值都是選取他下面兩個元素的較大值，并與自己相加得到的
			if(a[i+1][j] > a[i+1][j+1])  
				rec[i][j]+=a[i+1][j];
			else 
				rec[i][j]+=a[i+1][j+1];
	return rec[0][0];
}
           

動态規劃解法

通過遞歸的算法，我們可以得到一個動态規劃的狀态：dp[i][j]表示在目前位置，由上到下的路徑的值之和。

int dp_triangle(int n)  //三角形的行數作為參數
{
	int i,j;
	for(i=n-2;i>=0;i--)     //從倒數第二行開始計算，倒數第二行的計算是基于最後一行的， 
		for(j=0;j<=i;j++)
			dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
	return dp[0][0];
}
           

動态規劃算法的運作結果

這裡可以注意到原來的數組已經被相應位置，從下到上計算的最長路徑值更新了。