Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.
- At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
- Any two restaurants must be at least 2 miles apart.
A problem I was asked: suppose a file that stored many valid IPv4 addresses was corrupted such that all dot in the addresses were removed. Given such a corrupt IP, infer all possible corresponding IP addresses. For example, given 12345, all possible addresses are: 188.8.131.52, 184.108.40.206, 220.127.116.11 and 18.104.22.168. The hint that recursion should be used made the problem easier: