climbing stairs easy problem
Different ways you can climb a stair given that you can climb 1 or 2 steps.
package main
import (
"fmt"
)
func climbStairs(n int) int {
if n <= 0 {
return 0
} else if n <= 2 {
return n
}
prev1, prev2 := 1, 2
for i := 3; i <= n; i++ {
prev1, prev2 = prev2, prev1+prev2
}
return prev2
}
func main() {
n := 0
fmt.Printf("Number of ways to climb %d steps: %d\n", n, climbStairs(n))
}
What if you can take 1 or 3 step instead of 2 steps? Then it would be (n-1) + (n-4) and the code becomes :-
As you can see here, it is important to build up the base cases (the core numbers) that we will use for calculation here.
Position[1] => 1
Position[2] => 1
Position[3] => 1
Position[4] => 2
So given we have n = 5, we will have
(5-1) + (5-4) => Position[4] + Position[1] = base on the chart/position above, we get the value to add together [2] + [1] = 3
package main
import (
"fmt"
)
func climbStairs(n int) int {
if n == 0 {
return 1
}
if n == 1 {
return 1
}
if n == 2 {
return 1
}
if n == 3 {
return 1
}
if n == 4 {
return 2
}
// Initialize base cases
a, b, c, d := 1, 1, 1, 2 // f(1)=1, f(2)=1, f(3)=1, f(4)-2
for i := 5; i <= n; i++ {
next := d + a // f(n) = f(n-1) + f(n-4)
a, b, c, d = b, c, d, next
}
return d
}
func main() {
n := 5
fmt.Printf("Number of ways to climb %d steps: %d\n", n, climbStairs(n))
}
Comments