Hotel Stops

hotel.cpp

// C++11

// State subproblem in words
// Common case is to apply same problem to prefix of input
// That case seems to hold here

// Let dp[i] be the minimum cost of ending a night at position i

// Identify recursion

// dp[i] = min( dp[j] + cost(j,i) ) for all j < i

// The minimum cost of ending a night at position i is equal to
//   the minimum cost of ending a night at a prior position j plus the cost to travel from position j to i
//   we must consider all j less than i and take the minimum

#include <vector>
#include <iostream>
#include <cmath>
#include <numeric>

// Compute the cost for travelling from point a0 to a1
int cost(int a0, int a1) {
  return pow((200 - abs(a0 - a1)), 2);
}

int hotel(std::vector<int> &nums) {

  std::vector<int> pnums = nums; // Copy the numbers
  pnums.insert(pnums.begin(),0); // Zero pad at beginning

  // Initialize all elements to INT_MAX
  std::vector<int> dp(pnums.size(),INT_MAX);

  // The cost to stay at starting point is zero
  dp[0] = 0;

  for(int i = 1; i < dp.size(); i++)  
    for(int j = 0; j < i; j++)
      dp[i] = std::min(dp[j]+cost(pnums[i],pnums[j]), dp[i]);

  return dp[pnums.size()-1];   

}

int main() {

  std::vector<int> nums = {65, 120, 189, 250, 420, 600};

  std::cout << hotel(nums) << std::endl;

  return 0;

}