How to solve this dynamic programming?

Question

I practice DP and I came across this question. http://www.spoj.com/problems/MPILOT/en/

Charlie acquired an airline company and in order to stay in business, he needs to cut costs as little as possible. For his company, there are N pilots (N equals), and it is necessary to complete the assembly of N / 2 aircraft. The plane consists of two pilots - the captain and his assistant. The captain must be older than his assistant. Each pilot has a contract giving him two possible salaries: one as a captain, and the other as an assistant. The captain's salary is greater than the assistant for the same pilot. However, it is possible that the assistant has a higher salary than his captain. Write a program that calculates the minimum amount of money that Charlie should give for the salary of the pilots, if he decides to spend some time to make the optimal (i.e. the cheapest) arrangement of the pilots in the crews.

Enter

The first line of input contains an integer N, 2 ≤ N ≤ 10000, N is equal to the number of pilots working at Charlie. The next N lines of input contain the salary of the pilots. The lines are sorted by their flying age, the first salary of the younger pilot. Each of these N lines contains two integers separated by a space character, X i Y, 1 ≤ Y <X ≤ 100 000, salary as captain (X) and salary as helper (Y).

Exit

The first and only line of output should contain the minimum amount of money that Charlie should give for the salary of the pilots.

After research, I found out that this will be decided by DP, but how exactly will I resolve it? I spent several hours reading links, but I did not get what is easy to understand. Please help me.

Answer 1

, . , , - - .

---

, . , :

• N/2 N/2.
• , , , .

" " : 1 , 2 , 2-, .

"" . . , , . , ( 2) ( 1), ( , ) , () (b) (c) . . , , .

---

O (N ^ 2) -time. , , , K , C 0 [K/2] K-C C . N/2 N/2 . Untested 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

Answer 2

: , ; 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

Answer 3

. , , Y ( ) X ( ) , , --- (. ).

, node , :

                    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]

.