I sat down for this one at the end of the night hoping to take a look at it before bed and get a sense of the problem for tomorrow. Johannesburg turned out to be a fairly small modification of Montevideo and I was able to get a working attempt string in twenty minutes or so.
The way we, as an industry, interview prospective individual contributors is exhausting and ineffective. The goal of these interviews is to hire engineers who can design and implement simple, maintainable software, so why are we asking them contrived questions about dynamic programming? Engineers ought to be at least competent programmers, but the work of software engineering is more often a question of design.