Find N-th Tribonacci Number using Golang:
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)
}
0 Comments