I heard the only difference between dynamic programming and back tracking is DP allows overlapping of sub problems, e.g.
fib(n) = fib(n-1) + fib (n-2)
Is it right? Are there any other differences?
Also, I would like know some common problems solved using these techniques.
There are two typical implementations of Dynamic Programming approach: bottom-to-top and top-to-bottom.
Top-to-bottom Dynamic Programming is nothing else than ordinary recursion, enhanced with memorizing the solutions for intermediate sub-problems. When a given sub-problem arises second (third, fourth...) time, it is not solved from scratch, but instead the previously memorized solution is used right away. This technique is known under the name memoization (no 'r' before 'i').
This is actually what your example with Fibonacci sequence is supposed to illustrate. Just use the recursive formula for Fibonacci sequence, but build the table of fib(i) values along the way, and you get a Top-to-bottom DP algorithm for this problem (so that, for example, if you need to calculate fib(5) second time, you get it from the table instead of calculating it again).
In Bottom-to-top Dynamic Programming the approach is also based on storing sub-solutions in memory, but they are solved in a different order (from smaller to bigger), and the resultant general structure of the algorithm is not recursive. LCS algorithm is a classic Bottom-to-top DP example.
Bottom-to-top DP algorithms are usually more efficient, but they are generally harder (and sometimes impossible) to build, since it is not always easy to predict which primitive sub-problems you are going to need to solve the whole original problem, and which path you have to take from small sub-problems to get to the final solution in the most efficient way.
Dynamic problems also requires "optimal substructure".
According to Wikipedia:
Dynamic programming is a method of solving complex problems by breaking them down into simpler steps. It is applicable to problems that exhibit the properties of 1) overlapping subproblems which are only slightly smaller and 2) optimal substructure.
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
For a detailed discussion of "optimal substructure", please read the CLRS book.
Common problems for backtracking I can think of are:
DP problems:
Say that we have a solution tree, whose leaves are the solutions for the original problem, and whose non-leaf nodes are the suboptimal solutions for part of the problem. We try to traverse the solution tree for the solutions.
Dynamic programming is more like BFS: we find all possible suboptimal solutions represented the non-leaf nodes, and only grow the tree by one layer under those non-leaf nodes.
Backtracking is more like DFS: we grow the tree as deep as possible and prune the tree at one node if the solutions under the node are not what we expect.
Then there is one inference derived from the aforementioned theory: Dynamic programming usually takes more space than backtracking, because BFS usually takes more space than DFS (O(N) vs O(log N)). In fact, dynamic programming requires memorizing all the suboptimal solutions in the previous step for later use, while backtracking does not require that.
One more difference could be that Dynamic programming problems usually rely on the principle of optimality. The principle of optimality states that an optimal sequence of decision or choices each sub sequence must also be optimal.
Backtracking problems are usually NOT optimal on their way! They can only be applied to problems which admit the concept of partial candidate solution.
IMHO, the difference is very subtle since both (DP and BCKT) are used to explore all possibilities to solve a problem.
As for today, I see two subtelties:
BCKT is a brute force solution to a problem. DP is not a brute force solution. Thus, you might say: DP explores the solution space more optimally than BCKT. In practice, when you want to solve a problem using DP strategy, it is recommended to first build a recursive solution. Well, that recursive solution could be considered also the BCKT solution.
There are hundreds of ways to explore a solution space (wellcome to the world of optimization) "more optimally" than a brute force exploration. DP is DP because in its core it is implementing a mathematical recurrence relation, i.e., current value is a combination of past values (bottom-to-top). So, we might say, that DP is DP because the problem space satisfies exploring its solution space by using a recurrence relation. If you explore the solution space based on another idea, then that won't be a DP solution. As in any problem, the problem itself may facilitate to use one optimization technique or another, based on the problem structure itself. The structure of some problems enable to use DP optimization technique. In this sense, BCKT is more general though not all problems allow BCKT too.
Example: Sudoku enables BCKT to explore its whole solution space. However, it does not allow to use DP to explore more efficiently its solution space, since there is no recurrence relation anywhere that can be derived. However, there are other optimization techniques that fit with the problem and improve brute force BCKT.
Example: Just get the minimum of a classic mathematical function. This problem does not allow BCKT to explore the state space of the problem.
Example: Any problem that can be solved using DP can also be solved using BCKT. In this sense, the recursive solution of the problem could be considered the BCKT solution.
Hope this helps a bit.
DP allows for solving a large, computationally intensive problem by breaking it down into subproblems whose solution requires only knowledge of the immediate prior solution. You will get a very good idea by picking up Needleman-Wunsch and solving a sample because it is so easy to see the application.
Backtracking seems to be more complicated where the solution tree is pruned is it is known that a specific path will not yield an optimal result.
Therefore one could say that Backtracking optimizes for memory since DP assumes that all the computations are performed and then the algorithm goes back stepping through the lowest cost nodes.
In a very simple sentence I can say: Dynamic programming is a strategy to solve optimization problem. optimization problem is about minimum or maximum result (a single result). but in, Backtracking we use brute force approach, not for optimization problem. it is for when you have multiple results and you want all or some of them.
I did not find good answer, so let me try to answer it.
DFS, Depth First Search is brute-force, basically explores every single possiblity, it can go to the very leaf node in call-tree. It is simple thing. We can make slight changes in DFS, and create different Algorithms.
Backtracking is modification of DFS. What makes it Backtraking is our ability to reject the solution early instead of going to the very end. This is why it is called Backtracking, because we are continuously coming back mid-way when we reject a solution early. Examples are N-Queens and Sudoku. Note that we don't have to put all the N-Queens on Board to see if a solution is not-valid, we can do that early. Same with Sudoku.
(personal opinion)
We natually do not return our solution through return statement in Backtracking,(but we can), we develop it in the States, and might use the return statement to convey completeness-status(True/False) of our solution.
In Backtracking, we (generally) maintain a State that is shared across all the function calls and are continuously "making changes" to the state, e.g. ChessBoard in N-Queens and Board in Sudoku. DFS and Backtracking have similar code template.
DP without memoization is also just DFS. It also attempts to explore all possiblities. What makes it DP, is overlaping subproblems, so that we can use already computed values and avoid recomputing same things. In DP don't attempt to find "all solutions", we just want an optimum one. Like maxValue in Knapsack, which is just an integer value; in contrast with Sudoku or PowerSet. So it is easy to return the answer in DP problems through return statement because it is natural to do so, we are not building up a solution like in Sudoku or PowerSet, we just need one integer ans. We use subproblem to compute currentSolution. DP problems have clear induction-hypothesis about how the subproblems can be used to compute currentSolution; Backtracking do not have this property. (If you exploit hard enough, even Sudoku-Backtracking can have induction-hypothesis, but it is not natural)
Sumarry
If it requires to explore all possiblities, it involves DFS.
If early rejection is possible, it is Backtracking.
If there is Overlaping Subproblems and Optimal Substructure Property, then we can improve brute-force DFS's performance using DP. If we have these two properties, then the function must have a clear induction-hypothesis
Optimal Substructure Property: Ability to use Subproblems to compute current solution
Hope it helps.
Depth first node generation of state space tree with bounding function is called backtracking. Here the current node is dependent on the node that generated it.
Depth first node generation of state space tree with memory function is called top down dynamic programming. Here the current node is dependant on the node it generates.
Backtracking explores all possible solutions by trying each option and undoing choices when they lead to a dead end. It's useful for problems where all solutions need to be examined, like puzzles.
Dynamic programming, on the other hand, solves problems by breaking them into smaller subproblems, storing the results of solved subproblems, and reusing them to avoid redundant calculations. It's efficient for optimization problems.
In addition to @hesd10's amazing answer, another key difference between Dynamic Programming (DP) and BackTracking (BT) is that DP can only be applied to problems that can be broken down into smaller sub-problems while BT can be applied to anything that can be brute-forced.
So for instance, the example you gave of Fibonacci series would be a great fit for DP because by definition the Fibonacci(n) depends on calculating Fibonacci(n-1).
Another good example of DP would be Longest Palindromic Substring (LC-5 : https://leetcode.com/problems/longest-palindromic-substring/description/) where you can say that a string is a longest palindromic string if it's sub-string obtained by removing the left and right edge characters also forms a palindrome. Essentially you have broken down saying that a string is the longest-palindromic string if it's sub-string is a palindromic string.
On the other hand, traversing a maze is a good example of BT because you essentially go down all the paths and you discard the paths that give you a dead end. This is not a good candidate for DP because the problem cannot be broken-down into smaller sub-problems with a base case. To solve the problem, you have to brute force going down all the paths.
Essentially, DP is using BFS where you can break-down a problem into similar sub-problems and then choosing the optimal path. If you cannot break-down a problem into smaller similar sub-problem with a base case, you cannot use DP. BT is DFS where you can discard the sub-tree that doesn't lead to the solution. In that sense, BT is a more efficient alternative to going brute-force on every possible solution tree because you are discarding entire sub-trees that you know won't lead to a solution.
