Dynamic programming dependence on greater states

Question

There are N number of cities. Each city has a teleport of type 1 to 10(inclusive). You are given an array of size N representing each city's teleport type by integer. For ex. 1 3 5 3 8 9. The goal is to find the minimum amount of hours it takes to get from the first entry in the array to the last given the following rules:

1. From each city (entry in the array) you can move to it's left or right neighbor (if it has one) and that action costs 1 hour.
2. From each city you can teleport to another one with the same type of teleport as the one you're teleporting from. In the example array above you could teleport from the city at index 1 to city at index 3 because they both have the same type of teleport: 3. This action costs a given number R of hours.

I have implemented a dynamic programming solution that works perfectly fine when the fastest way is only moving forward. But for some cases, it's quicker to go back few cities to then teleport forward, thus minimizing the amount of hours spent.

This is an example of when my algorithm fails: ex. 2 1 3 4 6 8 5 7 4 2 3 5 2 1 3 4 3 5 6 7 and R = 2 Correct answer: index 0 (time = 0) -> index 9 (time = 2) -> index 8 (time = 3) -> index 7 (time = 4) -> index 19 (time = 6). My algorithm would find the quickest way only moving forwards, when clearly, the correct quickest way also involves moving backwards.

Here's my code so far:

#include <iostream>
using namespace std;

int main()
{
    int dp[200] = {};
    short ti[200] = {};
    int numCities, R;
    cin >> numCities >> R;

    for (int i = 0; i < numCities; i++)
    {
        short temp;
        cin >> temp;
        ti[i] = temp;
    }

    for (int i = 1; i < numCities; i++)
    {
        dp[i] = dp[i - 1] + 1;

        for (int x = i - 1; x >= 0; x--)
        {
            if (ti[x] == ti[i])
            {
                if (R + dp[x] < dp[i])
                     dp[i] = R + dp[x];
            }
        }
    }

    cout << dp[numCities - 1];

    return 0;
}

How do I make my algorithm work for these kind of cases, where a lower state depends on a greater one?

EDIT: I use dynamic programming the following way: For each of the cities, I compute the quickest way to get to them given the starting state dp[0] = 0. Then the recurrence relation is: dp[i] = min(dp[i - 1] + 1, dp[every other point with same teleport type] + R)

Answer 1

Dynamic programming works in instances where the problem has an optimal substructure. That is, you have to find a way to subdivide a problem such that the best solution to the subdivisions can be used as a building-block to find the best solution to the entire problem.

Above, I see you say that you want to use dynamic programming. And I see code. What I don't see is a clear explanation of what sub-problems you're considering. That is: a conceptual understanding of the solution is key to getting dynamic programming right, and this is exactly what you do not provide.

My instinct is that dynamic programming is not a good way to go in this instance since:

• Re-arranging the entries in the array destroys information about local movements
• It is possible, from the starting point, to move to any entry in the array - an inherent non-localism.

You cope with these issues by using a nested loop. This gives you an O(n^2) time solution.

However, considering this problem as an instance of weighted graph traversal allows you to solve it using Dijkstra's algorithm in O(n log n + m) time (an O(n) traversal being sufficient to establish each node's neighbors) where m is the number of edges considered (here it is possible to limit this to a value of Θ(m) by recognizing that each teleporter type will only be used once). Why not do this?

You could try to improve run-times by using A*, though I'm not convinced this will provide much improvement in one dimension.

Code to accomplish this might look like the following:

#include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>

typedef std::unordered_map<int, std::vector<int> > tele_network_t;

int Dijkstra(const std::vector<int> &graph, const tele_network_t &tn, const int R){
  //This whole mess makes the smallest elements pop off the priority queue first
  std::priority_queue<
    std::pair<int, int>,
    std::vector< std::pair<int, int> >,
    std::greater< std::pair<int, int> >
  > pq; //<distance, index>

  //Keeping track of the teleporters used allows us to speed up the algorithm by
  //making use of the theorem that each teleporter type will be used only once.
  std::unordered_set<int> teleporters_used; 

  //Keep track of the path
  std::vector<int> parent(graph.size(),-1); //Parent==-1 indicates an unvisited node

  //At 0 distance, place the 0th node
  pq.emplace(0,0);
  parent[0] = 0; //The only node whose parent is itself should be node 0

  while(!pq.empty()){
    const auto c = pq.top();
    pq.pop();

    //We've reached the goal node
    if(c.second==graph.size()-1){
      std::cout<<"Dist = "<<c.first<<std::endl;
      break;
    }

    //Insert neighbours
    if(c.second!=0 && parent[c.second-1]==-1){ //Left neighbour
      parent[c.second-1] = c.second;
      pq.emplace(c.first+1,c.second-1);
    }
    if(parent[c.second+1]==-1){ //Right neighbour: can't overflow because goal is the rightmost node
      parent[c.second+1] = c.second;
      pq.emplace(c.first+1,c.second+1);
    }

    //Inner loop is executed once per teleporter type
    if(teleporters_used.count(graph[c.second])==0)
      for(const auto i: tn.at(graph[c.second])){
        if(parent[i]==-1){
          pq.emplace(c.first+R,i);
          parent[i] = c.second;
        }
      }

    teleporters_used.insert(graph[c.second]);
  }

  //Trace our steps backwards to recover the path. Path will be reversed, but a
  //stack could be used to fit this.
  int p = graph.size()-1;
  while(parent[p]!=p){
    std::cout<<p<<std::endl;
    p = parent[p];
  }
  std::cout<<0<<std::endl;
}

int main(){
  tele_network_t tele_network;

  const int R = 2;
  std::vector<int> graph = {{2,1,3,4,6,8,5,7,4,2,3,5,2,1,3,4,3,5,6,7}};

  //Determine network of teleporters
  for(int i=0;i<graph.size();i++)
    tele_network[graph[i]].push_back(i);

  Dijkstra(graph, tele_network, 2);
}