【动态规划】【中位数】【C++算法】1478. 安排邮筒

# 作者推荐

【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目

本文涉及知识点

动态规划汇总

LeetCode1478. 安排邮筒

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的最小总和。
答案保证在 32 位有符号整数范围以内。
示例 1：
输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。
示例 2：
输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。
示例 3：
输入：houses = [7,4,6,1], k = 1
输出：8
示例 4：
输入：houses = [3,6,14,10], k = 4
输出：0
提示：
n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10⁴
1 <= k <= n
数组 houses 中的整数互不相同。

动态规划

原理

houser[i,j]之间安装邮筒，安装到正中间的房子是最优解。
a,假定房子数是奇数，假定共有2n+1个房子。假定左边有i1个房子，右边有i2个房子。如果i1 < i2，则右移可以缩短距离;i1 > i2，则左移可以缩短距离。如果邮筒不在屋子上，则i1永远不会等于i2。i1==i2，则必定在最中间的屋子。i+(j-i)/2。
b，屋子为偶数，在中间的两坐房子之间，才会让i1和i2。其实中间两间房子的任何一间房子都可以。
可以统一为：i+(j-i)/2
确切的说： $\begin{cases} 左边及本身的房子数小于右边的房子数，右移动。\\ 右边及本身的房子数小于左边的房子数，左移动。\\ \end{cases}$ $\rightarrow$ 稳定状态下，必须
$\begin{cases} i1 >=i2,i1 <=i2 \rightarrow i1==i2 & 邮筒不在房子上 \\ i1+1>=i2,i2+1 >= i1 \rightarrow abs(i1-i2)<=1 & 邮筒在房子上\\ \end{cases} \rightarrow$
如果房子数量是奇数
$\begin{cases} 邮筒不在房子上& i1==i2 \rightarrow (i1+i2)是偶数 \rightarrow 房子总数是奇数矛盾 \\ 邮筒在房子上且i1等于i2 & 正中间的房子 \\ 邮筒在房子上且i1和i2相差1 & 假定11+1=i2 \rightarrow i1+i2+1是偶数，和总数是奇数矛盾 \\ \end{cases} \rightarrow$ 如果房子的数量是奇数则只能安装在最中间。
如果房子数量是偶数
$\begin{cases} 邮筒不在房子上& i1==i2 \rightarrow 中间两间房子的空地 \\ 邮筒在房子上且i1等于i2 & i1+i2+1是奇数，与假设矛盾 \\ 邮筒在房子上且i1和i2相差1 & 中间任意两间房子 \\ \end{cases} \rightarrow$
如果房间数是偶数，则中间的两间房子及之间的空地都是最优解。

预处理

vDis[i][j] ，记录一个邮筒到house[i,j]的距离之和。houses要先排序。

动态规划的状态表示

dp[i][j] 表示 j个邮筒支持前i栋房最小距离。

动态规划的状态方程

通过前者状态更新后置状态。
$\Large_{k=1}^{i+k <= houses.length}$ pre[i+k][j+1] = min( $\cdots$ ,pre[i][j]+vDis[ $\cdots$ ])

动态规划的初始值

dp[0][0]=0 ，其它INT_MAX，表示非法值。

动态规划的填表顺序

i从小到大,j从小到大。

动态规划的返回值

dp.back()[k]

代码

核心代码

class Solution {
public:
	int minDistance(vector<int>& houses, int K) {
		m_c = houses.size();
		sort(houses.begin(), houses.end());
		vector<vector<int>> vDis(m_c, vector<int>(m_c));
		for (int center = 0; center < m_c; center++)
		{
			{
				int iDis = 0;
				for (int i = center, j = center; (i >= 0) && (j < m_c); i--, j++)
				{
					iDis += houses[j] - houses[i];
					vDis[i][j] = iDis;
				}
			}
			{
				int iDis = 0;
				for (int i = center, j = center + 1; (i >= 0) && (j < m_c); i--, j++)
				{
					iDis += houses[j] - houses[i];
					vDis[i][j] = iDis;
				}
			}
		}
		vector<vector<int>> dp(m_c + 1, vector<int>(K + 1, INT_MAX));
		dp[0][0] = 0;
		for (int i = 0; i <= m_c; i++)
		{
			for (int j = 0; j < K; j++)
			{
				if (INT_MAX == dp[i][j])
				{
					continue;
				}
				for (int m = 1; m + i <= m_c; m++)
				{
					dp[m + i][j + 1] = min(dp[m + i][j + 1],dp[i][j]+vDis[i][i+m-1]);
				}
			}
		}
		return dp.back().back();
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<int> houses;
	int k;
	{
		Solution sln;
		houses = { 7,4,6,1 };
		k = 1;
		auto res = sln.minDistance(houses, k);
		Assert(8, res);
	}
	{
		Solution sln;
		houses = { 1, 4, 8, 10, 20 };
		k = 3;
		auto res = sln.minDistance(houses, k);
		Assert(5, res);
	}
	{
		Solution sln;
		houses = { 2,3,5,12,18 };
		k = 2;
		auto res = sln.minDistance(houses, k);
		Assert(9, res);
	}
	
	{
		Solution sln;
		houses = { 3,6,14,10 };
		k = 4;
		auto res = sln.minDistance(houses, k);
		Assert(0, res);
	}
}

2023年2月版

class Solution {
public:
int minDistance(vector& houses, int k) {
const int iNotMay = 1000 * 1000 * 10;
std::sort(houses.begin(), houses.end());
m_c = houses.size();
vector pre(m_c);
for (int i = 0; i < m_c; i++)
{
pre[i] = Cost(houses, 0, i + 1);
}
for (int iK = 2; iK <= k; iK++)
{
vector dp(m_c, iNotMay);
for (int iHouse = 0; iHouse < houses.size(); iHouse++)
{
for (int pr = 0; pr < iHouse; pr++)
{
if (iNotMay == pre[pr])
{
continue;
}
dp[iHouse] = min(dp[iHouse], pre[pr] + Cost(houses, pr+1, iHouse + 1));
}
}
pre.swap(dp);
}
return pre.back();
}
int Cost(const vector& houses,int left, int r)
{
int iCost = 0;
int iMean = houses[left + (r - left) / 2];
for (int i = left; i < r; i++)
{
iCost += abs(houses[i] - iMean);
}
return iCost;
}
int m_c;
};

2023年7月版

class Solution {
public:
int minDistance(vector& houses, int k) {
m_c = houses.size();
sort(houses.begin(), houses.end());
vector<vector> vCost(m_c, vector(m_c));
for(int i= 0 ;i < m_c; i++ )
for (int j = i+1; j < m_c; j++)
{
int iMidValue = houses[i] + (houses[j] - houses[i]) / 2;
int cost = 0;
int k = i+1;
for (; houses[k] <= iMidValue; k++)
{
cost += houses[k] - houses[i];
}
for (; k < j; k++)
{
cost += houses[j] - houses[k];
}
vCost[i][j] = cost;
}
const int iNotMay = 1000 * 1000 * 10;
vector<vector> dp(m_c + 1, vector(k + 1, iNotMay));
dp[0][0] = 0;
dp[0][1] = 0;
vector vBegin(m_c);
{
int iSum = 0;
for (int i = 1; i < m_c; i++)
{
iSum += (houses[i] - houses[i - 1]) * i;
vBegin[i] = iSum;
}
}
for (int i = 1; i < m_c; i++)
{
for (int prePos = 0; prePos < i; prePos++)
{
for (int preK = 0; preK < k; preK++)
{
if (iNotMay == dp[prePos][preK])
{
continue;
}
if (0 == preK)
{
dp[i][preK + 1] = vBegin[i];
continue;
}
dp[i][preK + 1] = min(dp[i][preK + 1],dp[prePos][preK] + vCost[prePos][i]);
}
}
}
vector vEnd(m_c);
{
int iSum = 0;
for (int i = m_c - 2; i >= 0; i–)
{
iSum += (houses[i + 1] - houses[i]) * (m_c - 1 - i);
vEnd[i] = iSum;
}
}
int iRet = iNotMay;
for (int i = k-1; i < m_c; i++)
{
iRet = min(iRet, dp[i][k] +vEnd[i]);
}
return iRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛