Dynamic Programming with Go.
2 min readMay 10, 2024
###
The problem is below.
Given:
An array heights where heights[i] represents
the height of the ith position or stone.
Objective:
Calculate the minimum cost required for a frog
to traverse from the first stone to the last stone.
The frog can jump from a stone to the next one or skip one stone.
The cost of a jump is defined as the absolute difference in height
between the starting and ending stone of the jump.
Details:
The frog starts at the first stone (position 0 in the array).
From any stone i, the frog can jump to stone i+1 (next stone) or
i+2 (skip one stone).
The cost of a jump from stone i to stone j is |heights[j] - heights[i]|.
Output:
The minimum total cost for the frog to reach the last stone
from the first stone.The code I made is below.
package main
import (
"fmt"
"math"
)
func main() {
N := 7
heights := [7]int{2,9,4,5,1,6,10}
memo := []int{}
for index, _ := range heights {
if index == 0 {
memo = append(memo, 0)
} else if index == 1 {
memo = append(memo, memo[index-1] + abs(heights[index] - heights[index-1]))
} else {
memo = append(memo, min(memo[index-1] + abs(heights[index] - heights[index-1]), memo[index-2] + abs(heights[index] - heights[index-2])))
}
}
fmt.Println(memo)
fmt.Println(memo[N-1]) // 8
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func abs(n int) int {
return int(math.Abs(float64(n)))
}The time complexity is O(N).
What if I solve this problem straight-forwardly, which means I calculate all patterns?
package main
import (
"fmt"
"math"
)
func main() {
N := 7
heights := []int{2, 9, 4, 5, 1, 6, 10}
// Initialize a slice to store the minimum cost to reach each stone
cost := make([]int, N)
for i := range cost {
cost[i] = math.MaxInt32
}
// Cost to reach the first stone is zero because we start there
cost[0] = 0
// Compute the minimum cost to reach each stone
for i := 0; i < N; i++ {
for j := i + 1; j <= i+2 && j < N; j++ {
// Calculate the cost of jumping from stone i to stone j
jumpCost := abs(heights[j] - heights[i])
// Update the minimum cost to reach stone j
if cost[i]+jumpCost < cost[j] {
cost[j] = cost[i] + jumpCost
}
}
}
fmt.Println("Minimum cost to reach the last stone:", cost[N-1])
}
// Helper function to calculate the absolute difference
func abs(x int) int {
if x < 0 {
return -x
}
return x
}The time complexity is O(N²).
It is important to consider the time complexity.
