N-th Tribonacci Number using Golang

 Find N-th Tribonacci Number using Golang:

N-th Tribonacci Number

Solution without DP:


func tribonacciHelper(n, sum int, arr []int) int {
for i := 3; i <= n; i++ {
sum = arr[i-1] + arr[i-2] + arr[i-3]
arr[i] = sum
}
return sum
}


func tribonacci(n int) int {
array := make([]int, n+1)
if n== 0{
return 0
}
if n == 1 || n == 2{
return 1
}
array[0] = 0
array[1] = 1
array[2] = 1
return tribonacciHelper(n, 0, array)
}

Solution With DP:

func helper(n int, hashMap map[int]int) int {
if n == 0 {
return 0
}
if n == 1 || n == 2 {
return 1
}
if val, ok := hashMap[n]; ok {
return val
}
hashMap[n] = helper(n-1, hashMap) +
     helper(n-2, hashMap) + helper(n-3, hashMap)
return hashMap[n]
}

func tribonacci(n int) int {
hashMap := make(map[int]int, 0)
return helper(n, hashMap)
}

Post a Comment

0 Comments