题解 | 牛舍安排问题

1. 二维动态规划。
2. 难题。

import java.util.*;


public class Solution {
    public int minTotalDistance (int[] houses, int k) {
        final int n = houses.length;
        int[][] f = new int[n][k + 1];
        Arrays.sort(houses);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k + 1; ++j) {
                if (i == 0 || j == 0 || j >= i + 1) {
                    f[i][j] = 0;
                } else if (j == 1) {
                    f[i][j] = houses[i] - houses[0];
                } else {
                    int min = houses[n - 1] * n;
                    for (int x = 0; x < i; ++x) {
                        min = Math.min(min, f[x][j - 1] + Math.abs(houses[x+1] - houses[i]));
                    }
                    f[i][j] = min;
                }
            }
        }
        return f[n-1][k];
    }
}