Frog jump in swift || How to find min energy required ?

[Question] Find minimum total energy used by frog to reach from 1st stair to nth stair. He can jump from i+1 or i+2 stair.

// Approach 1: Using dynamic programming & recursion 
// Time complexity O(n)
// Space Complexity O(n)
func frogJump(_ n : Int, _ height: [Int], dp: inout [Int]) -> Int {
       dp[0] = 0
    for i in 1..<n {
        var fs = dp[i-1] + abs(height[i] - height[i-1])
        var ss = Int.max
        if i > 1 {
            ss = dp[i-2] + abs(height[i] - height[i-2])
        }
        dp[i] = min(fs, ss)

    }
    return dp[n-1]
}

var n = 6
var heights: [Int] = [30, 10, 60, 10, 60, 50]
var dp: [Int] = Array.init(repeating: -1, count: n+1)
let resultValue = frogJump(n, heights, dp: &dp)
print(resultValue)// output 40

// Approach 2: Using Tabulation (bottom up) Optimum space.
// Time complexity O(n)
// Space Complexity O(1)
func frogJump(_ n : Int, _ height: [Int]) -> Int {
    var prev1 = 0
    var prev2 = 0
    for i in 1..<n {
        var fs = prev1 + abs(height[i] - height[i-1])
        var ss = Int.max
        if i > 1 {
            ss = prev2 + abs(height[i] - height[i-2])
        }
        var curr = min(fs, ss)
        prev2 = prev1
        prev1 = curr
        
    }
    return prev1
}
var n = 6
var heights: [Int] = [30, 10, 60, 10, 60, 50]
let resultValue = frogJump(n, heights)
print(resultValue) // output 40

Leave a Comment

Your email address will not be published. Required fields are marked *