Maximize a traveling employee's vacation over k weeks
With this kind of problems it is important to build good mathematical model. After that, the best algorithm known to science can be easily found.

The problem in question seems to be Longest path problem, which if we build a graph properly has linear time solution.

Lets consider a graph (V, E), where V are week-offices (for example, H1, A1, B1, H2, A2, B2, ... - where H1 means home office at first week, B2 - office B at week two, and so on).

Edges are possible flights. For the example in the question we have the following edges:

H1 -> H2, H1 -> A2, H1 -> B2, H2 -> H3, A2 -> H3, B2 -> H3, H2 -> A3, H2 -> B3 (note, that there is never An -> Bn direct flights).

Here is the flights graph, which is an input, (on the left) and corresponding unrolled space-time one, for which a linear time algorithm can be found. Each node has a given weight.



Then a somewhat lengthy quotation from wikipedia:

"For instance, for each vertex v in a given DAG, the length of the longest path ending at v may be obtained by the following steps:


Find a topological ordering of the given DAG.
For each vertex v of the DAG, in the topological ordering, compute the length of the longest path ending at v by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If v has no incoming neighbors, set the length of the longest path ending at v to zero. In either case, record this number so that later steps of the algorithm can access it.


Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex v with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way."

Please, note, that our graph has been already topologically sorted - we know where it starts and where it ends.

A recursive algorithm can be elegant, but it's not really needed here.

This is maybe a bit unusual answer for a code review, but I strongly believe it is appropriate to point out at the possibility of a better algorithm while doing code review. I hope this is useful not only as a specific answer, but also as a good approach to apply math where it's due.

Please also note it is not necessary to memorize all possible graph and theory algorithms: At first I only had a vague idea, which became clear after some thinking and finding right terms.