考虑在一条单行道上有N个房子。我有M个路灯杆。假设 M < N。相邻房屋之间的距离不同。路灯杆只能放在房子上。我必须把所有路灯杆都放在房子上,以便每个房子到其最近灯杆的距离之和最小。如何编写此问题的代码?
经过一番研究,我发现需要使用动态规划来解决这个问题。但是我不知道如何处理这个问题。
经过一番研究,我发现需要使用动态规划来解决这个问题。但是我不知道如何处理这个问题。
O(n^2 * m)
的天真动态规划程序。也许其他人知道另一种加速方法?递归应该从代码中的函数f
清晰可见。// We can calculate these in O(1)
// by using our prefixes (ps) and
// the formula for a subarray, (j, i),
// reaching for a pole at i:
//
// ps[i] - ps[j-1] - (A[i] - A[j-1]) * j
//
// Examples:
// A: [1,2,5,10]
// ps: [0,1,7,22]
// (2, 3) =>
// 22 - 1 - (10 - 2) * 2
// = 5
// = 10-5
// (1, 3) =>
// 22 - 0 - (10 - 1) * 1
// = 13
// = 10-5 + 10-2
function sumParts(A, j, i, isAssigned){
let result = 0
for (let k=j; k<=i; k++){
if (isAssigned)
result += Math.min(A[k] - A[j], A[i] - A[k])
else
result += A[k] - A[j]
}
return result
}
function f(A, ps, i, m, isAssigned){
if (m == 1 && isAssigned)
return ps[i]
const start = m - (isAssigned ? 2 : 1)
const _m = m - (isAssigned ? 1 : 0)
let result = Infinity
for (let j=start; j<i; j++)
result = Math.min(
result,
sumParts(A, j, i, isAssigned)
+ f(A, ps, j, _m, true)
)
return result
}
var A = [1, 2, 5, 10]
var m = 2
var ps = [0]
for (let i=1; i<A.length; i++)
ps[i] = ps[i-1] + (A[i] - A[i-1]) * i
var result = Math.min(
f(A, ps, A.length - 1, m, true),
f(A, ps, A.length - 1, m, false))
console.log(`A: ${ JSON.stringify(A) }`)
console.log(`ps: ${ JSON.stringify(ps) }`)
console.log(`m: ${ m }`)
console.log(`Result: ${ result }`)
ps
变量是一种特殊的前缀和,它显示了从索引0到i
元素的所有距离之和。在这段代码中,它仅用于if (m == 1 && isAssigned)
以返回从开头到i
的所有距离之和,但我在注释中解释了如何将sumParts
循环转换为一个公式,用于具有右侧极点的子数组的所有距离之和(当极点在左侧时,我们需要第二个反转的ps
)。 - גלעד ברקןi
被分配了,我们需要使用二分查找或预先计算的表来找到点p
,将子数组分成从p
到i
的距离和从p-1
到j
的距离,因为每个房子都与更靠近它的电线杆相关。@KamalPancholi - גלעד ברקן我来帮你了解。首先,我会写下动态规划算法的解释,如果你无法编码,告诉我。
A -> 包含点的数组,使得A [i] - A [i-1]将是A [i]和A [i-1]之间的距离。 A [0]是第一个点。当您进行自顶向下的记忆化时,您将不得不处理以下情况:您想在当前房屋放置灯杆还是想将其放置在较低的索引处。如果现在放置它,您将使用一个更少的灯杆可用进行递归,并计算与前面房屋的距离之和。当您没有剩余任何灯杆或完成所有房屋时,您处理基本情况。