The Dynamic programming method
It can be described as follows: solve each small problem once, saving their solution; use the solutions of small problems to obtain solutions to larger problems.
The difference between dynamic programming problems and divide and conquer problems is the fact that the sub problems are not independent.
Scope: Dynamic programming algorithms are mostly used for optimization problems. For example the shortest path problem in a directed staged network, Neural networks, some economic applications. To be able to use dynamic programming, the problem must have certain properties:
1) Simple sub problems: There must be a way to break the big problem into smaller sub problems. Sub problems must be identified with just a few indices.
2) Sub problem optimization: An optimal solution to the big problem must always be a combination of optimal solutions to the sub problems.
3) Sub problem overlap: Optimal solutions to unrelated problems can contain sub problems in common.
Calculating Fibonacci numbers: After two starting values,each number is the sum of the two preceding numbers. For example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657…
using namespace std;
int main()
{
int Fib[1000]; //define array for fib numbers
Fib[0]=0; //define the first two Fibonacci numbers
Fib[1]=1;
for(int i=2;i<1000;i++) //get other Fibonacci numbers by adding the two preceding
Fib[i]=Fib[i-2]+Fib[i-1]; //Fibonacci numbers
}
Thanks ,
this is what I have searched for…
btw, nice site, keep going..