Dynamic Programming with Go.

Tomoharu Tsutsumi
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.

Feel free to reach out to me on LinkedIn, which you can find below. Looking forward to connecting!

https://www.linkedin.com/in/tomoharu-tsutsumi-56051a126/

--

--

Tomoharu Tsutsumi
Tomoharu Tsutsumi

Written by Tomoharu Tsutsumi

Senior Software Engineer at two industry-leading startups ( Go | Ruby | TypeScript | JavaScript | Gin | Echo | Rails | React | Redux | Next)

No responses yet