There are 100 steps, which can be taken 1 step or 2 steps, so how many ways do one walk?
Today's phone interview. When you encounter an algorithm problem, you will be confused in an instant;
Then, I was smart and thought that if a person takes 1 step every time, then he would have at most 100 steps, and at least 50 steps each time; then he obviously went off topic. . . Fortunately, the other party interrupted me in time. . . Otherwise, I would probably have to keep my brainstorm on this thing. . . Walking all the way to black. .
Then I got home. Holding my mac and thinking quietly, I finally wrote it out
var Stairs = new step();function step(){ this.n1=1; this.n2=2; this.total=100; this.getFunction = getFunction;}function getFunction(){ for(i=2;i<this.total;i++){ res = this.n1 + this.n2; this.n1 = this.n2; this.n2 = res; } return res;}var totalStairs = Stairs.getFunction();alert(totalStairs)When there is only 1 square. Only 1 step. . . . Just one type
When there are only 2 boxes, you can 1+1||2. . . 2 kinds
When there are 3 grids, 1+1+1||2+1||1+2. . 3 kinds
When 4 squares are 1+1+1+1||2+2||2+1+1||1+1+2||1+2+1. . . 5 kinds
sn = s(n-1)+s(n-2)
Fibonacci algorithm...and then it can be used
for(i=2;i<this.total;i++){ res = this.n1 + this.n2; this.n1 = this.n2; this.n2 = res;}Maybe I am not particularly good at algorithms~ If you have any objections, please correct me.
The above is the JS interview questions brought to you by the editor--the entire content of the algorithm level. I hope everyone will support Wulin.com more~