A Dynamic Programming problem. You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. …