专栏首页Krains1478. 安排邮筒 Krains 2020-07-30 14:51:32 动态规划DFS数学

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

# 题目链接

本题跟410. 分割数组的最大值 差不多,该题的题解

思路:将这条街分为几块区域,每个区域安排一个邮筒。在一个区域中,要想邮筒到该区域所有房子的距离之和最小,邮筒应该安排在这些房子位置的中位数上,这时邮筒到它们的距离总和最小(可由绝对值不等式证明)。

# DFS记忆化

首先先求出区域[i, j]安排一个邮筒的到区域内各个房子距离之和最小值,然后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;
    }
}

# 动态规划

状态表示

  • 集合:(i,j)(i, j)(i,j)表示前i所房子分配j个邮筒的所有分法。
  • 属性:f(i,j)f(i, j)f(i,j)表示所有分法中各个房子到其最近邮筒的距离最小和。

状态计算/集合划分

假设最后一个划分位置在k,k∈[0,i]k\in[0, i]k∈[0,i],那么

f(i,j)=f(k−1,j−1)+cost[k][i]f(i,j)=f(k-1,j-1)+cost[k][i] f(i,j)=f(k−1,j−1)+cost[k][i]

表示将前k-1所房子分配j-1个邮筒的距离最小和加上本次分配的邮筒所产生的距离和。

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];
    }
}	

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=h9nz2zbl70v8

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前缀和与差分 Krains 2020-07-28 16:05:15

    s[i]=a[0]+a[1]+a[2]+...+a[i−1]s[i] = a[0]+a[1]+a[2]+...+a[i-1]s[i]=a[0]+a[1]+a[2...

    Krains
  • 435. 无重叠区间 Krains 2020-07-28 11:26:10 贪心

    Krains
  • 410. 分割数组的最大值 Krains 2020-08-29 20:21:39 动态规划二分查找

    对答案进行二分,得到mid,如果mid可以将数组切割成m组,并且每组之和小于mid,由于我们要找的是满足要求的最小值,所以可以排除区间(mid, right],...

    Krains
  • T4701 【卜卜】树状数组模板

    题目描述 在二维平面内给定n个点: 0 x y v表示给(x,y)的权值减去v 1 x y v表示给(x,y)的权值加上v 然后有m个操作 0 x y v ,...

    attack
  • TopcoderSRM679 Div1 250 FiringEmployees(树形dp)

    有一个 \(n\) 个点的树,每个点有点权(点权可能为负) ,求包含点\(1\)的最 大权连通子图(的权值和) 。 \(n \leqslant 2500\)

    attack
  • 查找(上)

    AngelNH
  • 风险度量

    题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。 两个空间站间可能直接通信,也可能通过其它空间站中转。

    用户4492257
  • ViewDragHelper使用笔记及侧滑菜单实践

    佛系编码
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • Android Studio 2.2 JNI编译及Rxjava使用初级背景

    用户1127566

扫码关注云+社区

领取腾讯云代金券