如何攻克Hackerrank的Fair Cut挑战？求DP递推关系思路

首先得说，你之前用中位数+双指针的思路能过10个测试用例已经不错了，但这个问题确实没法靠贪心彻底解决——一旦数组里有极端值或者分布不均匀，贪心就会掉链子，比如我碰到过一个例子：数组是[1,3,4,5,10]，要选2个数给Li，贪心选中间的4和5得到的不公平度是21，但选3和5反而能得到20，更小。所以必须用动态规划来建模。

接下来我一步步给你推导递推关系，核心是先把数组排序，这是关键！因为排序后绝对值的计算可以直接转化为加减，不用再考虑正负。

第一步：问题转化与排序 #

先把数组从小到大排序，记为a₁ ≤ a₂ ≤ ... ≤ aₙ。这样一来，任何两个数的绝对值差都可以直接用大的减小的，不用判断顺序，这会极大简化后续的代价计算。

第二步：定义DP状态 #

我们需要两个二维数组：

• dp[i][j]：表示在前i个数里选j个给Li时，能得到的最小不公平度。
• g[i][j]：对应dp[i][j]的最优选择下，Li拿到的j个数的总和。（这个数组是关键，因为我们需要它来计算新增的不公平度）

另外预处理一个前缀和数组s，s[i] = a₁ + a₂ + ... + aᵢ，用来快速计算前i个数的总和。

第三步：初始状态 #

• dp[0][0] = 0：0个数里选0个，不公平度为0。
• g[0][0] = 0：对应的总和也是0。
• dp[i][0] = 0：前i个数选0个给Li，不公平度为0（Li没数，自然没有差值）。
• g[i][0] = 0：总和为0。
• dp[0][j] = ∞（无穷大）：0个数里选j>0个，不可能，用无穷大表示不可行。

第四步：状态转移 #

对于第i个数（也就是当前处理到aᵢ），我们有两种选择：分给Li，或者分给Lu。

选择1：把aᵢ分给Li

此时前i-1个数里已经选了j-1个给Li。新增的不公平度来自aᵢ和前i-1个数里分给Lu的那些数的差值——因为数组排序了，aᵢ比前i-1个数都大，所以每个差值都是aᵢ - y（y是前i-1个里Lu的数）。

前i-1个数里Lu的数有(i-1) - (j-1) = i-j个，它们的总和是s[i-1] - g[i-1][j-1]（前i-1个数的总和减去Li拿到的j-1个数的总和）。所以新增的代价是：
aᵢ*(i-j) - (s[i-1] - g[i-1][j-1])

对应的总不公平度就是：

cost1 = dp[i-1][j-1] + aᵢ*(i-j) - (s[i-1] - g[i-1][j-1])

此时Li的总和更新为：

sum1 = g[i-1][j-1] + aᵢ

选择2：把aᵢ分给Lu

此时前i-1个数里已经选了j个给Li。新增的不公平度来自aᵢ和前i-1个数里Li的那些数的差值——同样因为排序，每个差值都是aᵢ - x（x是前i-1个里Li的数）。

Li的j个数总和是g[i-1][j]，所以新增的代价是：
j*aᵢ - g[i-1][j]

对应的总不公平度就是：

cost2 = dp[i-1][j] + j*aᵢ - g[i-1][j]

此时Li的总和不变：

sum2 = g[i-1][j]

取最优解

我们选cost1和cost2里较小的那个作为dp[i][j]，同时把对应的总和赋值给g[i][j]：

if cost1 < cost2:
    dp[i][j] = cost1
    g[i][j] = sum1
else:
    dp[i][j] = cost2
    g[i][j] = sum2

第五步：空间优化（可选） #

因为计算dp[i][j]只需要用到dp[i-1][...]的状态，所以可以把二维数组改成一维的滚动数组，把空间复杂度从O(nk)降到O(k)，对于n较大的情况（比如n=1000）会更高效。

最终答案 #

填充完整个dp数组后，dp[n][k]就是Li恰好拿到k个数时的最小不公平度。

这样建模的核心是利用排序后的有序性，把绝对值差的计算转化为可累加的代价，同时通过维护Li的总和来快速计算新增的不公平度，避免了重复计算。

内容的提问来源于stack exchange，提问作者Rahul Seetharaman