Analysis: Partitioning the Farm by Jonathan Paulson

The small constraint on N suggests that the solution will be exponential time. The most obvious idea is to check all 2^(2N-2) possible wall positions, but this is too slow.

However, there are only 2^(N-1) possible choices for the vertical walls. And given a particular set of vertical walls, we can use dynamic programming to solve for the optimal placement of horizontal walls.

Specifically, let f(ROW, K) be the minimum possible size of the largest group of cows in rows [ROW...n] using K fences, given that there is a fence just above ROW. For the recurrence, we just pick the next fence: f(ROW, K) = min_{ROW+1 <= NEXT < N} COST[ROW][NEXT] + f(NEXT, K-1) where COST[ROW][NEXT] is defined as the maximum sum between rows ROW and NEXT for the current set of vertical walls.

Assuming we precompute COST, this DP runs in O(N^3) time (there are O(N^2) states and N transitions from each state). It turns out we can also precompute cost in O(N^3) time, so our total runtime will be O(2^N * N^3), which is fast enough.

Here is Richard Peng's code to precompute cost: 

for(int i = 0; i < n; ++i) {
        memset(s, 0, sizeof(s));
        for(int i1 = i + 1; i1 <= n; ++i1) {
          cost[i][i1] = 0;
          int s1 = 0;
          for(int j = 0; j < n; ++j) {
            s[j] += v[i1 - 1][j];
            s1 += s[j];
            cost[i][i1] = max(cost[i][i1], s1);
            if((mask >> j) % 2 == 1) {
              s1 = 0;
            }
          }
        }
      }
s is the array of column sums from row i to i1. s1 is the size of the current group of cows. mask is the current set of vertical walls. Every time we increase i1, we do O(N) work to update the column sums and compute the new max-sized group of cows. Here is Richard Peng's C++ solution: 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int VERYBIG = 1<<30;
const int MAXN = 20;

int n, k;
int v[MAXN][MAXN];

int ans;

int DP[MAXN][MAXN], cost[MAXN][MAXN], s[MAXN];

int main() {
  freopen("partition.in", "r", stdin);
  freopen("partition.out", "w", stdout);
  scanf("%d%d", &n, &k);
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < n; ++j) {
      scanf("%d", &v[i][j]);
    }
  }
  ans = VERYBIG;
  for(int mask = 0; mask < (1<<(n - 1)); ++mask) {
    int k1 = 0;
    for(int i = 0; i < n; ++i) {
      k1 += (mask >> i) % 2;
    }
    if(k1 <= k) {
      for(int i = 0; i < n; ++i) {
        memset(s, 0, sizeof(s));
        for(int i1 = i + 1; i1 <= n; ++i1) {
          cost[i][i1] = 0;
          int s1 = 0;
          for(int j = 0; j < n; ++j) {
            s[j] += v[i1 - 1][j];
            s1 += s[j];
            cost[i][i1] = max(cost[i][i1], s1);
            if((mask >> j) % 2 == 1) {
              s1 = 0;
            }
          }
        }
      }
      for(int k2 = 0; k2 <= n; ++k2) {
        for(int i = 0; i <= n; ++i) {
          DP[k2][i] = VERYBIG;
        }
      }
      DP[0][0] = 0;

      for(int k2 = 1; k2 <= n && k2 <= (k - k1 + 1); ++k2) {
        for(int i = 0; i < n; ++i) {
          for(int i1 = i + 1; i1 <= n; ++i1) {
            DP[k2][i1] = min(DP[k2][i1], max(DP[k2 - 1][i], cost[i][i1]));
          }
        }
        ans = min(ans, DP[k2][n]);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}