题意

给出n*m的矩阵，可以横着切一刀或是竖着切一刀，问切完后两块和的差值的最小值

思路1：暴力枚举

首先能想到的是O(n^3)的暴力，以横着切一刀为例，枚举切的位置是i，那么1~i 行的元素之和就是第一块的值s1，i+1~n行的元素之和就是第二块的值s2，大概的代码如下

for i := 1; i <= n; i++ {
		//切的位置
		var s1,s2 int64 = 0,0
		for k := 1; k <= i; k ++ {
			for j := 1; j <= m; j ++ {
				s1 += int64(a[k][j])
			}
		}
		for k := i+1; k <= n; k ++ {
			for j := 1; j <= m; j ++ {
				s2 += int64(a[k][j])
			}
		}
		ans = min(ans,abs(s1-s2))
	}

思路2：一维前缀和

思路1会有很多重复计算的地方，而且数组a是不变的数组，所以可以预处理下需要计算的信息，以减少时间复杂度。

还是以横着切为例，枚举当前切的位置为i，那么对于每个位置i来说，第一块的面积是前i行矩阵元素的和，第二块的面积是i+1行到n行矩阵元素的和，那么我们只需要用前缀和数组sum1[x]表示前x行矩阵元素的和就可以了。

竖着切也同理。

golang代码一直超时只能用cpp写了，要注意开long long

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    vector<long long> sum1(n + 1, 0), sum2(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int tmp = 0;
        for (int j = 1; j <= m; ++j) {
            tmp += a[i][j];
        }
        sum1[i] = sum1[i - 1] + tmp;
    }
    for (int j = 1; j <= m; ++j) {
        int tmp = 0;
        for (int i = 1; i <= n; ++i) {
            tmp += a[i][j];
        }
        sum2[j] = sum2[j - 1] + tmp;
    }
    long long ans = 1e9;
    for (int i = 1; i <= n; ++i) {
        long long s1 = sum1[i] - sum1[0];
        long long s2 = sum1[n] - sum1[i];
        ans = min(ans, abs(s1 - s2));
    }
    for (int j = 1; j <= m; ++j) {
        long long s1 = sum2[j] - sum2[0];
        long long s2 = sum2[m] - sum2[j];
        ans = min(ans, abs(s1 - s2));
    }
    cout << ans << endl;
    return 0;
}

思路3：二维前缀和

核心点和思路2一样，不过换了种实现方法。

还是以横着切为例，如果当前切的位置是i的话，那么第一块的大小是sum[i][m] ，第二块的大小是sum[n][m]-sum[i][m]，这样的话就是默认把左上角的节点看成矩形的左上角。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    vector<vector<long long>> sum(n + 1, vector<long long>(m + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + a[i][j];
        }
    }

    long long ans = 1e9;
    // 枚举横着切还是竖着切
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, abs(sum[n][m] - sum[i][m] * 2));
    }
    for (int j = 1; j <= m; ++j) {
        ans = min(ans, abs(sum[n][m] - sum[n][j] * 2));
    }
    cout << ans << endl;
    return 0;
}