1478. 安排邮筒 Krains 2020-07-30 14:51:32 动态规划DFS数学

class Solution {
    // cost[i][j]表示在区域[i, j]中安排一个邮筒到该区域其他房子的距离之和的最小值
    int[][] cost;
    int n;

    public int minDistance(int[] houses, int m) {
        Arrays.sort(houses);
        n = houses.length;
        cost = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                for(int k = i; k <= j; k++){
                    cost[i][j] += Math.abs(houses[k] - houses[i+(j-i+1)/2]);
                }
            }
        }

        return helper(0, 0, m, new Integer[n+1][m+1]);
    }

    // [i, n)是待划分的区域，j表示当前第几个划分
    public int helper(int i, int j, int m, Integer[][] memo){
        if(memo[i][j] != null)
            return memo[i][j];

        // 划分结束且最后一组不为空，直接返回最后一组区域[i, n)要花费的代价
        if(j + 1 == m && i < n)
            return cost[i][n-1];

        int min = Integer.MAX_VALUE / 2;
        // 穷尽所有的划分点
        for(int k = i; k < n; k++){
            // [i, k]是当前划分，[k+1, n)是后面的划分
            min = Math.min(min, cost[i][k] + helper(k+1, j+1, m, memo));
        }

        // 记忆
        return memo[i][j] = min;
    }
}

class Solution {
    int[][] cost;
    int n;

    public int minDistance(int[] houses, int m) {
        Arrays.sort(houses);
        n = houses.length;
        cost = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = i; j < n; j++){
                for(int k = i; k <= j; k++){
                    cost[i][j] += Math.abs(houses[k] - houses[i+(j-i+1)/2]);
                }
            }
        }

        int[][] dp = new int[n][m+1];

        for(int i = 0; i < n; i++) 
            dp[i][0] = Integer.MAX_VALUE / 2;
        
        for(int i = 1; i < n; i++){
            for(int j = 1; j <= m; j++){
                dp[i][j] = Integer.MAX_VALUE / 2;
                for(int k = 0; k <= i; k++){
                    int t = 0;
                    if(k != 0) t = dp[k-1][j-1];
                    dp[i][j] = Math.min(dp[i][j], t + cost[k][i]);
                }
            }
        }

        return dp[n-1][m];
    }
}