Some thoughts on the problem:

• Dogs & Mice can be transposed together. In the other hand Elephants & Cats can be transposed together. Let's call Dogs & Mice as type1 animals, where Elephants & Cats as type2 animals.
• define an array maxTransports[0...numZoos], where maxTransports[i] represents max transports that can be done if we travel from zoo number 0 to zoo number i and leaving the car empty at zoo i.
• Base case: maxTransports[0] = 0 as problem restrictions specify that:
  • s_i != d_i
  • we can visit zoos only in increasing order, i.e. if there's some s_i > d_i, this animal can't be transposed.
• So, it's always s_i < d_i. And as there's no zoo before zoo 0, there's no animal that can be transposed to zoo 0.
• Recursive case: for 1 <= i <= numZoos, maxTransports[i] = max of:
  • maxTransports[j] + num of type1 transports in the range j-->i where 0 <= j < i
  • maxTransports[j] + num of type2 transports in the range j-->i where 0 <= j < i
• Explanation:
  • we move from zoo 0 to any zoo j that's before zoo i, tranporting the max amount of animals to zoo j, then leaving the car empty. This is represented by the first part which is maxTransports[j].
  • As the car is left empty at zoo j, we can use it to transpose all animals of the same type (type1 or type2) from any zoo x (where j <= x <= i) to any zoo y (where x <= y <= i). This is represented by the second part of the recursive equation.
• The only challenging part is that, for each zoo i, we have to traverse all zoos before it. this should take O(numZoos^2). If there's a way to reduce the number of zoos that should be checked, this solution can pass all test cases.

Any suggestions?