TopCoder Open 2012 Round 1C Div1 Medium PasswordXGrid

問題

hxwのグリッドがあり、(0,0)から右か下へ移動することを繰り返し、(h,w)へ移動する。
それぞれの辺には1から9までの数字が割り振られている。

どのような経路をたどっても、ゴールへ移動するまでに通った辺の数字の和が一定になるように、辺の数字を変えたい。

辺の数字は、好きな正の整数だけ増やすことができる。（増やさなくてもよい）
ゴールへ移動するまでに通る辺の数字の和の最小値を求めよ。

制約条件

h,w≦50

方針

実はゴールまでの最長距離に合わせられるらしい。
Editorialの証明には、
longest(i,j)を、(i,j)からゴールまでの最長距離とすると、
longest(i,j) + e(i,j,i+1,j)≦ longest(i+1,j)が成り立つので、
eをlongest(i+1,j) - longest(i,j)へ変えることができる。

と書いてあった。
eを変えたらlongestも変わるんじゃないの？ってことで微妙に納得がいかない。

ソースコード

class PasswordXGrid {
	public:
	int minSum(vector <string> horizontal, vector <string> vertical) 
	{
		int w=vertical[0].size(), h = horizontal.size();
		int dp[50][50] = {};
		for(int i = h-1; i >= 0; i--) for(int j = w-1; j >= 0; j--){
			if(i) dp[i-1][j] = max(dp[i-1][j], dp[i][j] + vertical  [i-1][j] - '0');
			if(j) dp[i][j-1] = max(dp[i][j-1], dp[i][j] + horizontal[i][j-1] - '0');
		}
		return dp[0][0];
	}
};