There are several Fibonacci number related problems in LeetCode, which are generally solved using dynamic programming.
Later, I read the Code Interview Guide for Programmers: Algorithms for IT Famous Enterprises and Optimal Solutions for Data Structure Problems, and I learned that this kind of problem uses fast power to solve matrix products, which can be solved in log(N)log(N)log(N) time complexity.
For the convenience of review, the Fibonacci number and fast power related problems in LeetCode are unified.
Question list
509. Fibonacci numbers
Offer 10-i. Fibonacci sequence
1137. The NTH Tebonacci number
70. Climb the stairs
50. Pow(x, n)
746. Climb stairs at minimal cost
Dynamic programming solution
509. Fibonacci numbers
Same problem: Offer 10-i. Fibonacci sequence
Problem Description:
We can use dynamic programming to solve the Fibonacci number, and the solution process is as follows:
1, state: given the subscript NNN, find the value of F(n)F(n)F(n)
Dp []dp[]dp[], dp[n]dp[n]dp[n] dp[n]dp[n]
3, Base case: The boundary of Fibonacci sequence, dp[0]=0, DP [1]= 1DP [0]=0, DP [1]=1
4. State transition Equation:
The definition of Fibonacci sequence itself contains “state, array, base case, and state transition equation” of dynamic programming, and F(n)F(n)F(n) F(n)F(n) is only related to F(n−1), F(n−2)F(n −1), F(n−2)F(n −1), F(n−2)F(n −2), and F(n−2). Two variables can be used. To optimize the storage of arrays.
The code implementation is as follows:
class Solution {
public int fib(int n) {
final int MOD = (int) 1e9 + 7;
if (n <= 1) {
return n;
}
int f1 = 0, f2 = 1;
for (int i = 2; i <= n; i++) {
int f3 = (f1 + f2) % MOD;
f1 = f2;
f2 = f3;
}
returnf2; }}Copy the code1137. The NTH Tebonacci number
Problem Description:
The problem solving thinking and 509 Fibonacci Numbers are similar, the difference is that T T (n) (n) T (n) and T (n – 1), T (n – 2) and T (n – 3) T (n – 1), T (n – 2) and T (n – 3) T (n – 1), T (n – 2) and T (n – 3) are related.
The code implementation is as follows:
class Solution {
public int tribonacci(int n) {
if (n == 0) {
return 0;
} else if (n <= 2) {
return 1;
}
int num1 = 0, num2 = 1, num3 = 1;
for (int i = 3; i <= n; i++) {
int tmp = (num1 + num2 + num3);
num1 = num2;
num2 = num3;
num3 = tmp;
}
returnnum3; }}Copy the code70. Climb the stairs
Problem Description:
When this problem is solved using dynamic programming, the state transition equation is the same as the Fibonacci number. The solution process is as follows:
1. State: Given the number of steps NNN, the way to reach NNN is defined as F(n)F(n)F(n)
Dp []dp[]dp[] dp[]dp[n]dp[n]dp[n] dp[n]
3. Base case: one step or two steps can be climbed at a time to obtain boundary conditions, dp[1]=1, DP [2]= 2DP [1]=1, DP [2]= 2DP [1]=1, DP [2]=2
4. State transition Equation:
Step III can be reached by climbing one step from step I − 1i-1i −1, or climbing two steps from step I − 2i-2i −2, Therefore, the way to step III is the sum of “the way to step I − 1i-1i −1” and “the way to step I − 2i-2I −2”, and the transfer equation is as follows:
The solving process of dynamic programming is the same as the previous two problems.
The code implementation is as follows:
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int f1 = 1, f2 = 2, f3 = 0;
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
returnf3; }}Copy the codeThe previous three problems are simple sequential dynamic programming problems, which can be solved in O(N)O(N)O(N) time complexity by using the dynamic programming method introduced above.
Is there a faster way to do that? Can I do it in log(N)log(N)log(N) time? This requires the use of the quick powers described below.
Fast power
Fast powers algorithm description, from Reference reading: Fast powers
Algorithm description
Binary power
To compute aaa to the NNN power is to multiply NNN aaAs together:
When the values of A,na,na, and n are small, you can calculate them by traversing and multiplying them. But when the values of A,na,na, and n are very large, this method doesn’t work very well.
However, according to the exponentiation rules, we know that:
According to this rule, it can be solved by fast power algorithm. The basic idea of fast power is to express the exponent NNN in binary form, and then exponentiate it by binary bits. The exponentiation task can be divided into smaller computational tasks.
Convert the integer NNN to a binary representation. The bits of the binary representation are as follows: k=⌊log2n⌋+1 k= \lfloor \log_2 n \rfloor + 1K =⌊log2n +1. NNN is expressed as:
Aaa to the NNN power can be expressed as:
In the above formula, the index values of the product terms aaa are: 20=1,21=2,22=4… , 2 k2 ^ 0 = 1, 2 ^ 1 ^ 2 = 4 = 2, 2,… , 2 ^ k20 = 1, 2, 2 = 4,… 2k, the last number is the square of the previous number. Thus, knowing the value of a1a^{1}a1, ana^nan can be computed by θ (logn)\Theta(\log n) θ (logn) multiplication.
The sample
Let’s use an example (a=3,n= 13A =3,n= 13A =3,n=13) to illustrate the above calculation process.
We express NNN as base 2 and ana^nan as:
Where, the coefficient of each index 1,0{1,0}1,0 corresponds to the 1 and 0 values of each bit in the binary representation of NNN (1101)2(1101)_2(1101)2
According to the previous algorithm description, we can quickly calculate the values of the powers of 3, as shown below:
To calculate 3133^{13}313, we simply multiply the binary bits to the power of one.
The complexity of this algorithm is θ (logn)\Theta(\log n) θ (logn) :
- θ (logn)\Theta(\log n) θ (logn) to the power of 2 is calculated
- It takes θ (logn)\Theta(\log n) θ (logn) to multiply the binary bits by powers of 1
Code implementation
public int binaryExpo(int a, int n) {
int res = 1;
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = res * a;
}
// Every time you move a bit, change to the square of the previous bit
a = a * a;
n = n >> 1;
}
return res;
}
Copy the code50. Pow(x, n)
The problem of calculating power functions on LeetCode can be solved using the quick power solution described above. The code is as follows:
class Solution {
public double myPow(double x, int n) {
// n will exceed digits
long N = n;
N = Math.abs(N);
double res = binaryExpo(x, N);
if (n < 0) {
return 1 / res;
} else {
returnres; }}public double binaryExpo(double a, long n) {
double res = 1;
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = res * a;
}
// Every time you move a bit, change to the square of the previous bit
a = a * a;
n = n >> 1;
}
returnres; }}Copy the code
Fast exponentiation of matrix products
The following content, from the reference reading: Programmer code Interview Guide: IT Enterprise Algorithm and data structure problem optimal solution
How can fast powers be used to solve Fibonacci numbers?
Fibonacci number transfer equation: F (n) = F (n – 1) + F (n – 2) F (n) = F (n – 1) + F (n – 2) F (n) = F (n – 1) + F (n – 2), can be writing in the form of matrix multiplication:
The calculation formula of Fibonacci number can be expressed as:
We need to compute the n−2n-2n−2 power of the matrix. We can modify the code we used to compute fast powers to compute matrix powers.
A quick power code for calculating a matrix is as follows:
/** * quick power of matrix **@paramMat matrix *@paramN power * /
public int[][] binaryExpo(int[][] mat, int n) {
int[][] res = new int[mat.length][mat[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = mulMat(res, mat);
}
// Every time you move a bit, change to the square of the previous bit
mat = mulMat(mat, mat);
n = n >> 1;
}
return res;
}
/** * computes two matrix multiplies: mat1 * mat2 **@paramMat1 matrix 1 star@paramMat2 matrix 2 */
public int[][] mulMat(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat1[0].length, l = mat2[0].length;
int[][] res = new int[m][l];
for (int i = 0; i < m; i++) {
for (int j = 0; j < l; j++) {
for (int k = 0; k < n; k++) { res[i][j] += mat1[i][k] * mat2[k][j]; }}}return res;
}
Copy the codeWith a fast power calculation method for matrices, you can use fast powers to calculate the previous problem.
Fast power solution
According to the previous analysis, Fibonacci number, Tibonacci number and stair climbing problem can all be calculated by using fast powers, and their differences only lie in different initial values and different state transition matrices.
The code implementation is as follows.
509. Fibonacci numbers
class Solution {
public int fib(int n) {
if (n < 1) {
return 0;
}
if (n <= 2) {
return 1;
}
int[][] res = binaryExpo(new int[] [] {{1.1}, {1.0}}, n - 2);
return res[0] [0] + res[1] [0];
}
public int[][] binaryExpo(int[][] mat, int n) {
int[][] res = new int[mat.length][mat[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = mulMat(res, mat);
}
// Every time you move a bit, change to the square of the previous bit
mat = mulMat(mat, mat);
n = n >> 1;
}
return res;
}
public int[][] mulMat(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat1[0].length, l = mat2[0].length;
int[][] res = new int[m][l];
for (int i = 0; i < m; i++) {
for (int j = 0; j < l; j++) {
for (int k = 0; k < n; k++) { res[i][j] += mat1[i][k] * mat2[k][j]; }}}returnres; }}Copy the code1137. The NTH Tebonacci number
class Solution {
public int tribonacci(int n) {
if (n <= 1) {
return n;
}
if (n <= 3) {
return n - 1;
}
int[][] res = binaryExpo(new int[] [] {{1.1.0}, {1.0.1}, {1.0.0}}, n - 3);
return 2 * res[0] [0] + res[1] [0] + res[2] [0];
}
public int[][] binaryExpo(int[][] mat, int n) {
int[][] res = new int[mat.length][mat[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = mulMat(res, mat);
}
// Every time you move a bit, change to the square of the previous bit
mat = mulMat(mat, mat);
n = n >> 1;
}
return res;
}
public int[][] mulMat(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat1[0].length, l = mat2[0].length;
int[][] res = new int[m][l];
for (int i = 0; i < m; i++) {
for (int j = 0; j < l; j++) {
for (int k = 0; k < n; k++) { res[i][j] += mat1[i][k] * mat2[k][j]; }}}returnres; }}Copy the code70. Climb the stairs
class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int[][] res = binaryExpo(new int[] [] {{1.1}, {1.0}}, n - 2);
return 2 * res[0] [0] + res[1] [0];
}
/** * quick power of matrix **@paramMat matrix *@paramN power * /
public int[][] binaryExpo(int[][] mat, int n) {
int[][] res = new int[mat.length][mat[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
while (n > 0) {
// The current bit is equal to 1, multiplied by the value of that bit
if ((n & 1) = =1) {
res = mulMat(res, mat);
}
// Every time you move a bit, change to the square of the previous bit
mat = mulMat(mat, mat);
n = n >> 1;
}
return res;
}
/** * computes two matrix multiplies: mat1 * mat2 **@paramMat1 matrix 1 star@paramMat2 matrix 2 */
public int[][] mulMat(int[][] mat1, int[][] mat2) {
int m = mat1.length, n = mat1[0].length, l = mat2[0].length;
int[][] res = new int[m][l];
for (int i = 0; i < m; i++) {
for (int j = 0; j < l; j++) {
for (int k = 0; k < n; k++) { res[i][j] += mat1[i][k] * mat2[k][j]; }}}returnres; }}Copy the code
summary
Compared with the traditional dynamic programming method, the fast power method can solve the problem in faster time complexity.
But in code implementation, dynamic programming is more simple, fast power comparison is more complex.
Other similar questions
746. Climb stairs at minimal cost
Problem Description:
70. When the state changes, add the cost of the current step and minimize it.
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
if (n == 1) {
return cost[0];
}
if (n == 2) {
return Math.min(cost[0], cost[1]);
}
int f1 = cost[0], f2 = cost[1], res = 0;
for (int i = 2; i <= n; i++) {
int cs = 0;
if (i < n) {
cs = cost[i];
}
res = Math.min(f1 + cs, f2 + cs);
f1 = f2;
f2 = res;
}
returnres; }}Copy the codeRefer to the reading
Fast power
matrix
Programmer code interview guide: IT enterprise algorithm and data structure problem optimal solution