我该如何解决这个动态规划问题？

Question

我正在练习动态规划，遇到了这个问题。 http://www.spoj.com/problems/MPILOT/en/ Charlie收购了一家航空运输公司，为了保持业务，他需要尽可能降低开支。 有N名飞行员在他的公司工作（N是偶数），并且需要组成N/2个机组。一个机组由两名飞行员组成-机长和他的助手。机长必须比他的助手年长。每位飞行员都有一份合同，授予他两种可能的薪水-一种是机长，另一种是助手。对于同一位飞行员而言，机长的薪水要高于助手的薪水。但是，助手的薪水可能比他的机长还高。编写一个程序，如果决定花费一些时间来制定飞行员组合的最佳（即最便宜）安排，则将计算Charlie需要支付的最小工资总额。

输入

输入的第一行包含整数N，2≤N≤10,000，N为偶数，表示Charlie公司工作的飞行员数量。接下来的N行输入包含飞行员的薪水。这些行按照飞行员的年龄排序，最年轻的飞行员的薪水排在第一位。每一行都包含两个由空格字符分隔的整数Xi和Yi，1≤Y< X ≤100,000，一个是船长的薪水（X），另一个是助手的薪水（Y）。

输出

输出的第一行应该包含Charlie需要支付给飞行员薪水的最少金额。

经过调查，我发现这可以通过DP来解决，但我该如何解决呢？我花了几个小时阅读链接，但没有一个容易理解的。请帮帮我。

- Harry Lewis

---

在我看来，要求SPOJ（Sphere Online Judge）的解决方案有点作弊。但我又算什么呢。 - Błażej Michalik

事实是，我真的很努力地尝试解决它，甚至想出了一个递归，但它没有给出正确的答案。我不知道出了什么问题。如果我的逻辑有误或其他原因，最终我在这里发布了它。我也不想这样做，但请帮我一下。这将不胜感激。谢谢！ :) - Harry Lewis

Answer 1

从左下角开始，即我们升序列表的起点，实际上有一种很好的可视化方法。我们可以将选择一个Y（助手的工资）作为向右移动和选择一个X（船长的工资）作为向上移动来想象，前提是不穿过西南-东北对角线（请参见维基百科中的 卡特兰数 ）。

从中我们可以看出，三角形中的每个节点最多有两个前任，来自西边或南边，因此自下而上的一般情况应该是：

                    captain               assistant
dp[i][j] = min(x[i+j-1] + dp[i-1][j], y[i+j-1] + dp[i][j-1])

Example:

x = [4,5,6,7]
y = [3,2,1,2]

            [9+7]
     [3+5]  [min(8+1,5+6)]
[.]  [3]    [3+2]

我会把编程留作练习。

- גלעד ברקן

Answer 2

通常情况下，我们需要找到一组紧凑的子问题。记住飞行员如何匹配的细节是不够的 - 我们需要像以下描述一样的东西。

---

考虑一种标记，使每个飞行员成为机长或助手，而不考虑匹配。当且仅当满足以下两个条件时存在有效匹配：

1. 有N/2个机长和N/2个助手。
2. 对于每个年龄截止点，有至少与该截止点年龄相比更年轻的助手与比该截止点年龄更年轻的机长一样多。

"只有如果"方向很容易：条件1是显然的，条件2成立是因为不等式对于每个2名飞行员组都成立，我们可以将这些不等式相加。

对于"如果"方向，我们实际上必须构建机组。我们通过归纳进行。如果没有飞行员，则空匹配是有效的。否则，由于最年轻的飞行员是助手（根据条件2），并且至少存在一个机长（根据条件1），因此存在（如果您想要花哨一点，可以使用Sperner引理）一对飞行员，使得（a）没有飞行员的年龄中间值（b）较年轻的人是助手（c）较老的人是机长。匹配这对并将其从池中删除。注意到两个条件仍然成立，因此按归纳假设匹配其余部分。

---

这个观察结果导致了一个O(N^2)时间的动态规划程序。我们反复读取下一个年龄最大的飞行员的薪水，然后计算，在考虑了K名飞行员之后，对于所有C从0到[K/2]，支付K-C个助手和C个队长中这些飞行员的最小成本。最后，返回支付N/2个助手和N/2个队长的成本。未经测试的Python代码如下：

def cost(pilots):
    cost = [0]
    for i, (assistant_salary, captain_salary) in enumerate(pilots):
        cost.append(float('inf'))  # two-way sentinel
        cost = [min(cost[c] + assistant_salary,
                    cost[c - 1] + captain_salary)
                for c in range((i + 1) / 2 + 1)]
    return cost[-1]  # i.e., N/2

- David Eisenstat

Answer 3

对于C++中的递归方法，您可以按照以下代码进行更好的理解：

int min_salary(int a[],int n,int x,int c[])
{
    if(n==0)
        return 0;
    if(x==0)
        return(a[0]+min_salary(a+1,n-1,1,c+1));
    if(x==n)
        return(c[0]+min_salary(a+1,n-1,x-1,c+1));
    else
        return(min(a[0]+min_salary(a+1,n-1,x+1,c+1),c[0]+min_salary(a+1,n-1,x-1,c+1)));
}

- Supriya

Answer 4

让我们为递归制定一些条件：如果我们到达了末尾，返回总和；如果我们有 N/2 个助手，则添加一个船长；如果我们剩下的助手和船长数量相同，则添加一个助手（我们不能有比助手年轻的船长）；否则，返回添加船长或助手的最小成本。

JavaScript 代码：

var x = [4,5,6,7];
var y = [3,2,1,2];
var n = x.length;

function f(i,ys,s){
  if (i == n){
    return s;
  }
  if (ys == n / 2){
    return f(i + 1,ys,s + x[i]);
  } else if (i % 2 == 0 && ys == i / 2){
    return f(i + 1,ys + 1,s + y[i]);
  } else {
    return Math.min(f(i + 1,ys + 1,s + y[i]),f(i + 1,ys,s + x[i]));
  }
}

输出：

console.log(f(0,0,0)) // 16

- גלעד ברקן