[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