Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
recursive-staircase solution
package main
import (
"fmt"
"bufio"
"os"
"strings"
"strconv"
)
func recurse(stairLen int, resultMap map[int]int) int {
if stairLen == 1 {
return 1
}
if stairLen == 2 {
return 2
}
if stairLen == 3 {
return 4
}
if _, ok := resultMap[stairLen - 3]; !ok {
resultMap[stairLen - 3] = recurse(stairLen - 3, resultMap)
}
if _, ok := resultMap[stairLen - 2]; !ok {
resultMap[stairLen - 2] = recurse(stairLen - 2, resultMap)
}
if _, ok := resultMap[stairLen - 1]; !ok {
resultMap[stairLen - 1] = recurse(stairLen - 1, resultMap)
}
if (stairLen - 3) > 0 {
return resultMap[stairLen - 3] + resultMap[stairLen - 2] + resultMap[stairLen - 1]
}
if (stairLen - 2) > 0 {
return resultMap[stairLen - 2] + resultMap[stairLen - 1]
}
if (stairLen - 1) > 0 {
return resultMap[stairLen - 1]
}
return 0
}
func main() {
reader := bufio.NewReader(os.Stdin)
readLine, _ := reader.ReadString('\n')
readLine = strings.TrimSuffix(readLine, "\n")
stairsCount, _ := strconv.Atoi(readLine)
resultMap := make(map[int]int, stairsCount)
for i := 0; i < stairsCount; i++ {
readLine, _ := reader.ReadString('\n')
stairLen, _ := strconv.Atoi(strings.TrimSuffix(readLine, "\n"))
fmt.Println(recurse(stairLen, resultMap))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.