Selecting lowest cost hotel rooms, with no adjacent rooms selected

Question

You and your friends (k friends in total, including yourself) are going to Hawaii for a vacation.  In Hawaii, you are given a choice of n hotel rooms, in a straight line, numbered from 1 to n.  The cost of the i-th room is c[i].  You can select any k hotel rooms, but you want to ensure that no two selected hotel rooms selected are adjacent to each other.  Your objective is to minimize the cost.  Describe an efficient algorithm for this problem.

Answer 1

• Notation: Suppose S(i,j) is the smallest cost of selecting j hotel rooms from 1..i hotel rooms
• The principle of optimality holds i.e., it has optimal sub-structure
•  Base Case S(1,1) = c[1]
• We need to find S(n,k).
• Recursive Formulation: S(i,j) = min { S(i-1,j), S(i-2,j-1) + c[i] }

Algorithm:

for i = 1 to n 

  for j = 1 to k 

    S(i,j) = min { S(i-1,j), S(i-2,j-1) + c[i] }

Time Complexity= O(nk)