There are feelings, there are dry goods, wechat search xiaoxi learning algorithm focus on this different program yuan.
GitHub github.com/ animation algorithm has been included, there are a line of large factory interview high-frequency algorithm problem solution, are explained by animation, each problem solution with at least 20+ is most likely to be the most careful algorithm problem solution, clear and easy to understand.
The title
Write a function, input n, to find the NTH term of the Fibonacci sequence. The Fibonacci sequence is defined as follows:
F (0) = 0, F (1) = 1, F (N) = F (N - 1) + F (N - 2), where N > 1Copy the code
The Fibonacci sequence starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.
1e9+7 (1000000007) is required for the answer. If the initial calculation result is 1000000008, return 1.
Source: LeetCode link: https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcofCopy the code
The interview scene
class Solution {
public int fib(int n) {
if(n == 0)
return 0;
if(n == 1)
return 1;
return fib(n - 1) + fib(n - 2); }}Copy the code
Go back to school
So if YOU compute fib of 6, you can see that f of 3 is repeated three times, and f of 4 is repeated twice, and you can imagine that the higher you go, the more times you’re going to repeat.
Mnemonic recursion
class Solution {
public int fib(int n) {
int [] arr = new int[n + 1];
for (int i = 0; i < arr.length;i++) {
arr[i] = -1;
}
return fibWithArray(n, arr);
}
public int fibWithArray(int n,int [] arr) {
if (n < 2) {
return n;
}
if (arr[n] == -1) {
arr[n] = (fibWithArray(n-1, arr) + fibWithArray(n-2, arr)) % 1000000007;
}
return arr[n];
}
}
Copy the code
Small evening: So my recursion was double counting, so I just opened up an array, and I initialized the array to be -1, and when the array was -1, Arr [N] = (fibWithArray(N-1, ARR) + fibWithArray(n-2, ARR)) % 1000000007; Arr [n] is not -1, so next time it is not -1. If (arr[n] == -1) if (arr[n] == -1) if (arr[n] == -1)
So, for example, if you compute f of 5, you can see from the previous picture, in order to compute f of 5, you have to compute f of 3 twice.
Here small evening I give an example is clear at a glance. Now you only need to use arrays once.
Mnemonic recursion example
Recursive animation
Xxi: So you can see, because of the array, when calculating f(5), f(4), f(3), f(2) is only computed once, that is to say, when calculating f(n), f(1) to f(n-1) is only computed once, which greatly reduces the time of recursion.
Dynamic programming solution
Ta: Yuki, your mnemonic recursion is top-down. The “dynamic programming” approach is “bottom-up”. In effect, the problem of small data size was solved “really” first, and the problem of large data size was solved step by step.
The Fibonacci sequence is defined by recursion, and by this recursive relationship, we can know the value of any position in the Fibonacci sequence.
The key to dynamic programming is to find the transition equation, what is the transition equation? You put thef(n)
I want to do a staten
, this staten
Is by the staten - 1
And state n - 2
This is called a state shift.
So it’s easy to get the state transition equation from the Fibonacci sequence: Dp [I +1] = DP [I] + DP [I −1] The initial state of the state transition equation is easy to know :dp[0] = 1 DP [1] = 1. The NTH Fibonacci sequence we want is dp[n], so according to the transition equation, the following code can be obtained:
class Solution {
public int fib(int n) {
if(n < 2)
return n;
int dp[] = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){ dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
}
returndp[n]; }}Copy the code
Dynamic programming optimization
Tubule TA: Dp [I] dp[i-1] dp[i-2], sum,b,a represent dp[I] dp[i-1].
- For example, in order to calculate DP [3], it is necessary to calculate first
dp[2] = dp[1] + dp[0]
. We don’t use arrays, which issum = b + a
. At this timesum =1 b = 1 a= 0
- In order to calculate DP [3], it is necessary to retain the calculation result of DP [2], which is sum.
- So we let
a = b = 1
That is, the result of leaving A to retain dp[1]b = sum = 1
That is, the result of leaving B to retain dp[2] - So dp[3] = b + a = 2
Let me give you a few examples.
Let’s animate it
The complexity of the
Because we don’t use arrays, it’s O(1) in space and O(n) in time.
Java solution
class Solution {
public int fib(int n) {
int a = 0;
int b = 1;
if(n == 0)
return 0;
if(n == 1)
return 1;
int i = 2;
int sum=0;
while(i <= n)
{
sum = (a + b) % 1000000007;
a = b;
b = sum;
i++;
}
returnsum; }}Copy the code
C + + solution
class Solution {
public:
int fib(int n) {
int a = 0;
int b = 1;
if(n == 0)
return 0;
if(n == 1)
return 1;
int i = 2;
int sum=0;
while(i <= n)
{
sum = (a + b) % 1000000007;
a = b;
b = sum;
i++;
}
returnsum; }};Copy the code
JS solution
/ * * *@param {number} n
* @return {number}* /
var fib = function(n) {
var a = 0;
var b = 1;
if(n == 0)
return 0;
if(n == 1)
return 1;
var i = 2;
var sum=0;
while(i <= n)
{
sum = (a + b) % 1000000007;
a = b % 1000000007;
b = sum;
i++;
}
return sum;
};
Copy the code
PY solution
class Solution(object) :
def fib(self, n) :
a = 0;
b = 1;
if(n == 0) :return 0;
if(n == 1) :return 1;
i = 2;
sum=0;
while(i <= n):
sum = (a + b) % 1000000007;
a = b;
b = sum;
i += 1;
return sum;
Copy the code
PHP solution
class Solution {
/ * * *@param Integer $n
* @return Integer
*/
function fib($n) {
$a = 0;
$b = 1;
if($n= =0)
return 0;
if($n= =1)
return 1;
$i = 2;
$sum=0;
while($i< =$n)
{
$sum = ($a + $b) % 1000000007;
$a = $b;
$b = $sum;
$i+ +; }return $sum; }}Copy the code
The GO method
func fib(N int) int {
a := 0;
b := 1;
if N == 0 {
return 0;
}
if N == 1 {
return 1;
}
sum := 0;
for i := 2; i <= N; i++ {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return sum;
}
Copy the code
The last
Xiao Xi finally have words
- Animation, comics, plus 6 programming languages (Java, C++, PHP, GO, Python, JS) explanation is very painstaking, I hope you can help forward to the circle of friends and friends around, so that xiao xi’s article can let more people see, xiao xi will be more motivated to update the article!
The last
The article continues to update, can be wechat search “xiaobi algorithm” for the first time to read, reply [666] I prepared for the first large factory interview high-frequency algorithm information, this article GitHub github.com/ animation algorithm has been included, there are animation algorithm solution is clear and easy to understand, welcome Star.