Imagine we are on a tour of some popular tourist spots and we wish to visit each one of them. They are all along a single road at mileposts m_0, m_1, m_2, ..., m_n, and we will stop at each one in that order. The choice we have to make is which taxi company to use to take us from one location to the next. The choices are taxi company S (slow) and Company T(tedious). Company S charges s_i dollars per mile to travel from location i to i + 1, so the charge for that segment is (m_i + 1 - m_i) middot s_i dollars. Company T charges a flat rate of t dollars per segment but if chosen they location i, have them take us to i + 1, i + 2, and finally finish with them at location i + 3 for a total of 3t dollars (of course, we could decide to use them for the next three segments). Our goal is to find the cheapest cost for all segments taking us from location 0 to location n. For example, suppose the mileposts are at locations (0, 25, 50, 100, 150, 200), the costs for company S are (2, 3, 2, 1, 2), and the flat rate for company T is 40. If the travel plan is (S, T, T, T, S), the travel cost is 25 middot 2 + 40 + 40 + 40 + 50 middot 2 = 270 dollars. However the plan (S, S, T, T, T) incurs a cost of 25 middot 2 + 25 middot 3 + 40 + 40 + 40 = 245 dollars. Define the subproblem C(i) to be the minimum cost of a plan that starts at location 0 and ends at location i, and so that (a) company S brought us from m_i - 1 to m_i (at a cost of s_i - 1 per mile, or (b) company T was used on the last three segments (from m_i - 3 to m_i - 2 to m_i - 1 to m_i). A recurrence for C is given by C(i) {0 if i = 0 (m_i - m_i - 1)middot s_i - 1 + C(i - 1) if 0