Dynamic planning learning notes

Dynamic programming learning notes

Dynamic programming

Fibonacci sequence

Fibonacci sequence Every number All are The sum of the first two digits of this number .

Fibonaccci Sequence
1	1	2	3	5	8	13	21

If we use a formula to represent any number in the sequence, it is (n>1)：
$$fib(n)=fib(n-1)+fib(n-2)$$
In code ：

long long fib(long long n){    // Find the... In the Fibonacci sequence n Number 
    if(n==1||n==2){  
        return n;  
    }
    return fib(n-1)+fib(n-2);  // Continue to recursive 
}

But when n large , Amount of computation It's just Extremely large , When we decompose each calculation of the computer, we will find many Repeat the calculation , And the larger the calculation , The more calculations are repeated , Then we have to use a method ： Dynamic programming .

Dynamic programming

Dynamic programming Is the opposite solution Optimization problems A kind of Design method or thought , It's not an algorithm , This method contains many algorithms , Such as recursive , decompose etc. . Dynamic programming solves more complex problems by decomposing the original problem into several sub problems .

One type, three signs

There are many people who are interested in Dynamic programming such Optimization plan Understand very thoroughly and make a summary , I summarize it as **“ One type, three signs ”**.

" Type I ” It refers to The optimal solution model .

“ Three signs ” refer to Optimal substructure 、 Subsequent invalidity and Memory search .

Optimization plan

First simulate a scenario ： The teacher arranged 100 A very complicated problem , But this 100 All the questions are the same , Then we only need to calculate the result of one problem , Just copy it to other questions ( Of course, you can also calculate one by one , But a person who really counts one by one must be a fool —）, And unfortunately , The computer is such a fool —, And then we can use it Memory search , Is to record the results of each calculation , If you need a certain calculation result in the subsequent calculation , Call directly .

// Use dynamic programming to solve Fibonacci sequence 
long long fib(long long n,long long* memo) {
	if (n == 1 || n == 2) return 1;
	if (memo[n] != 0) return memo[n];
	
	memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
	return memo[n];
}

summary ：

The focus of Dynamic Planning ：

1. decompose , Decompose the original problem into several sub problems .

2. One type, three signs , Make an optimal solution model for the problem , At a certain stage, once determined , It will not be affected by the later stage and memory search .

​ ... Here is the end , Here is the end ...