LeetCode1478.  安排邮筒

LeetCode1478. 安排邮筒

题目描述

image.png

方法1 动态规划

解决这道题我们需要理解以下4点

  • 假如只有1个邮筒,N个房子,显然这个邮筒放在最中间(中位数)可以使得所有房子到这个邮筒的距离最小
  • 于是我们可以把这道题转换为,怎么用邮筒去把房子分成若干个区域,每一个区域内在中位数放邮筒,然后求出最小的距离和 --> 这里就类似划分数组问题了,比如813. 最大平均值和的分组
  • 我们计算cost[i][j]表示从ij的区域内,放一个邮筒,[i:j]区域内到这个邮筒的最小距离之和
  • dp[i][j]表示从0~i区域的房子,放j个邮筒(分成j块)的最小距离之和;于是有dp[i][j] = MIN(dp[k-1][j-1] + cost[k][i]),k≤i
import java.util.Arrays;

public class Solution {

    public int superEggDrop(int K, int N) {class Solution {
    public int minDistance(int[] houses, int m) {
        int n = houses.length;
        int[][] cost = new int[n][n];
        Arrays.sort(houses);

        for(int i = 0;i<n;i++){
            for(int j=i;j<n;j++){
                int mid = i + (j - i + 1) / 2;
                for(int k=i;k<=j;k++){
                    cost[i][j] += Math.abs(houses[k] - houses[mid]);
                }
            }
        }

        int[][] dp = new int[n][m+1];
        for(int[] x:dp){
            Arrays.fill(x,(int)1e7);
        }

        for(int i=0;i<n;i++){
            for(int j=1;j<m+1;j++){
                for(int k = 0; k<=i;k++){
                    int t = (k>=1)?dp[k-1][j-1]:0;
                    dp[i][j] = Math.min(dp[i][j],t + cost[k][i]);
                }
            }
        }

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