An obviously cubic solution:

dp[0][0] = maze[0][0];
for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < m; j++) {
		if (i == 0 && j != 0) {
			continue;
		}
		int leftsum = 0;
		for (int k = j - 1; k >= 0; k--) {
			leftsum += maze[i][k];
			dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + leftsum + maze[i + 1][k]);
		}
		int rightsum = 0;
		for (int k = j + 1; k < m; k++) {
			rightsum += maze[i][k];
			dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + rightsum + maze[i + 1][k]);
		}
	}
}

The answer will be in dp[n - 1][m - 1].

Your strategy is solving problem with different set of moves.

It's problem from Timus Online Judge again :) Timus is offline now, so this is Google cache link: 1029 — Ministry.
One difference is that you should find the minimal path, not maximal.

We can solve it in O(n*m) time. We can use DP with 3 parameters — current row, current column, and another parameter, which describes the direction we used to get on our current cell.

UPD: Oh, there was a silly bug in previous implementation (I forgot that the matrix can contain negative numbers). So, I believe that the right code is in Rev.5

I hope it is true solution:

for(i = 1; i <= m; i++)
    dp[1][i] = sum[1][i];

for(i = 2; i <= n; i++){
    for(j = 1; j <= m; j++){
        dp[i][j] = -INF;
        for(k = 1; k <= m; k++){
            if(k<=j)
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][j] - sum[i][k-1]);
            else
                dp[i][j] = max(dp[i][j], dp[i-1][k] + sum[i][k] - sum[i][j-1]);
        }
    }
}

where sum[i][j] is sum of i'th row from 1 to j inclusive and dp[i][j] is the values of the longest sum of cells from cell (1, 1) to cell (i, j).

Answer will be in dp[n][m].

I think I have a linear time solution for this one, i'll post it soon.