why this basic conception is so important, Because you can use these
four to describe solution space. repeated permutation can be use in 0/1
backpack problem. LCS problem.
nearest point pair’s solution space is n*(n-1). It’s n2. A good hint is
that it can be reduce n * log(n). So We should consider D&C (divide
and conquer)
0/1 packback’s solution’s space is 2n, A good hint is that I can be
reduce to nc. (c is constant) by dynamic programming.
If there is not D&C or DP, you have to use branch and bound or
backtracking. such as TSP travelling sales problem
If you need optimal answer, You need to traversal the whole solution
space. ( such as TSP and 0/1 backpacking). If you don’t need optimal
answer, you don’t need to do that, In these two conditions, you all need
to backtracking.
Why I can’t use DP to TSP, but I can use DP to 0/1?
recursion is a mathematical induction.
modeling is mapping your problem to a abstract structure.