Dynamic Programming - Counting paths in a subway system

I have a network of stations in a subway system. The number of stations, the number of tickets I have to travel between stations, and which stations are connected to each other are given in a text file as input to the program. Which stations are connected to each other are kept in a 2D boolean matrix. I have to find the number of paths from station 0 and back to 0 that uses all of the tickets.

Here is one of the examples:

In that example, there are 7 stations and 5 tickets. Starting and returning to 0, there are 6 paths:

0-1-2-3-4-0
0-1-5-3-4-0
0-1-6-3-4-0
0-4-3-6-1-0
0-4-3-5-1-0
0-4-3-2-1-0

I currently have a recursive solution to this that runs in O(N^k) (N represents the number of stations while k is the number of tickets), but I have to convert it to an iterative, dynamic programming solution in O(k*N^2) that works on any input.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>

using namespace std;


// We will represent our subway as a graph using
// an adjacency matrix to indicate which stations are
// adjacent to which other stations.
typedef std::vector<int> row;
typedef std::vector<row> Matrix;

struct Subway {
  bool** connected;
  int nStations;

  Subway (int N);

private:
  // No copying allowed
  Subway (const Subway&) {}
  void operator= (const Subway&) {}
};


Subway::Subway(int N)
{
  nStations = N;
  connected = new bool*[N];
  for (int i = 0; i < N; ++i)
    {
      connected[i] = new bool[N];
      fill_n (connected[i], N, false);
    }
}

unsigned long long int callCounter = 0;
void report (int dest, int k)
{
  ++callCounter;
  // Uncomment the following statement if you want to get a feel 
  // for how many times the same subproblems get revisited
  // during the recursive solution.
  cerr << callCounter << ": (Destination: " << dest << ", Steps Left: " << k << ")" << endl;
}


/**
 * Count the number of ways we can go from station 0 to station destination
 * traversing exactly nSteps edges.
 */
unsigned long long int tripCounter (const Subway& subway, int destination, int nSteps)
{
    report (destination, nSteps);
    if (nSteps == 1)
    {
        // Base case: We can do this in 1 step if destination is
        // directly connected to 0.
        if (subway.connected[0][destination]){
            return 1;
        }
        else{
            return 0;
        }
    }
    else
    {
        // General case: We can get to destinaiton in nSteps steps if
        // we can get to station S in (nSteps-1) steps and if S connects
        // to destination.
        unsigned long long int totalTrips = 0;
        for (int S = 0; S < subway.nStations; ++S)
        {
            if (subway.connected[S][destination])
            {
                // Recursive call
                totalTrips += tripCounter (subway, S, nSteps-1);
            }
        }
        return totalTrips;
    }
}

// Read the subway description and
// print the number of possible trips.
void solve (istream& input)
{
  int N, k;
  input >> N >> k;
  Subway subway(N);
  int station1, station2;
  while (input >> station1)
    {
      input >> station2;
      subway.connected[station1][station2] = true;
      subway.connected[station2][station1] = true;
    }
  cout << tripCounter(subway, 0, k) << endl;
  // For illustrative/debugging purposes
  cerr << "Recursive calls: " << callCounter << endl;
}




int main (int argc, char** argv)
{
  if (argc > 1) 
    {
      ifstream in (argv[1]);
      solve (in);
    }
  else
    {
      solve (cin);
    }
  return 0;
}

I'm not looking for a solution. I am currently out of ideas and hoping someone can point me in the right direction. Since I'm required to implement a bottom-up approach for this, how would I start with developing a dynamic programming table using the smallest sub-problems?