洗襪子撈撈

7-3 最低通行費 (25 分)

問題描述

輸入格式:

第一行是一個整數，表示正方形的寬度N (1≤N<100)；

后面N行，每行N個不大于100的整數，為網格上每個小方格的費用。

輸出格式:

至少需要的費用。

輸入樣例:

5
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33



結尾無空行

輸出樣例:

109



結尾無空行

樣例中，最小值為109=1+2+5+7+9+12+19+21+33。

算法描述

從時間來看商人只能往下或者往左走,如果將橫坐標記為i,縱坐標記為j,則往下一步為(i,j+1),往右為(i+1,j)最小子問題就是min{(i,j+1),(i+1,j)},由于無法走出網格則限制條件為0<i,j<n.于是我們可以列出下圖的遞歸方程

問題求解:??為遞歸方程

??代碼實現

int f(int h,int l){
	if(dp[h][l]!=0) return dp[h][l];
	dp[h][l]=m[h][l];
	int t = 1e9;
	for(int i= 0; i < 2;i++){
		int sh = h +x[i][0],sl = l + x[i][1];
		if(sh >= 0 && sh < N && sl >= 0 && sl < N){
			t = min(t,f(sh,sl));
		}
	}

if(t!=1e9){dp[h][l]=t+m[h][l];}
return dp[h][l];}

t為定義一個極大的數方便找出第一個值

心得體會:

感受到算法的威力了,從遞歸調用產生巨大的時間復雜度到建立備忘錄再到放棄遞歸改成遞推最后消除多余數組減少空間復雜度,算法是一門值得深究的學科

對dp的理解和體會:

真正的四兩撥千斤算法,特別有意思