Another ingredient that optimization problems must have for dynamic programming to apply is that the space of subproblems should be small. Hence, a recursive algorithm for the problem should solve the same subproblems repeatedly. Typically, the total number of distinct subproblems is a polynomial in the input size. A recursive algorithm is said to have overlapping subproblems if it visits the same problem repeatedly. It's therefore typical for dynamic programming algorithms to cache solutions to subproblems to avoid re-computation of the same solutions over and over.