From n to n-1

For most DP and searching problems, it's vital to reduce the original problem of size n to a new problem of the same the with size n-1. It's gennerally good if a f(n) problem can be solved by a constant number of f(n-1) problem, resulting a DP. If we can only reduce it to h(n) problems of f(n-1), often it's an exhausting searching problem where pruning or memorizing technique must be used.

Of course, “n” mentioned above is not confined to an integer. It may refer to a pair like (p,q), if f(p,q) can be solved by solving f(p,q-1), it's also a DP.

Let's illustrate the above idea with an example. f is a function mapping a sequence a1, a2, a3, ..., aN to a value. If we can find a g, s.t.

f(a1,a2,...,aN) = g(f(a1,a2,...,aN-1))

and g is easy to compute(which is often the case), we are in a happy situation. If, on the other hand, we have to solve each N-1 sized problem: f(a2,...,aN), f(a1,a3,...,aN), f(a1,a2,a4,...,aN), ..., f(a1,a2,...,aN-1) before we know the value of f(a1,a2,...,aN), it's a costly search problem.

Unfortunately, the ideal reduction is often difficult to find while the costly one is almost always at hand. More often than not, the problems we face can be solved far more efficiently than we are first willing to believe.