Frog jumping problem and its dynamic programming solution in C++/Java.

Solving the Frog Jumping Problem with Dynamic Programming

Introduction

Imagine a frog positioned at the base of a staircase, with each step having a certain height. The frog wants to reach the top of the staircase, but it can only jump in two ways: by taking a single step or by taking a double step. Each step incurs a cost based on the difference in height between the current step and the previous one. The goal is to find the minimum cost for the frog to reach the top of the staircase.

This classic problem, known as the Frog Jumping Problem, can be efficiently solved using dynamic programming. In this blog post, we’ll explore the problem, its recursive nature, and then dive into an iterative dynamic programming solution implemented in C++.

The Problem

Let’s formalize the problem. Given an array heights representing the heights of the steps and an integer n indicating the number of steps, we want to find the minimum cost for the frog to jump from the first step to the last step.

Recursive Approach

One way to approach this problem is through recursion. We define a recursive function f(index, heights) that calculates the minimum cost to reach the step at the given index. The base case is when the frog is at the first step (index == 0), and the cost is zero. Otherwise, the cost is the minimum of two options: jumping from the previous step or jumping from two steps back.

int f(int index, vector<int> &heights) {
    if (index == 0) return 0;
int left = f(index - 1, heights) + abs(heights[index] - heights[index - 1]);
    int right = INT_MAX;
    if (index > 1) {
        right = f(index - 2, heights) + abs(heights[index] - heights[index - 2]);
    }
    return min(left, right);
}

public class Solution {
    public static int frogJump(int n, int heights[]) {
        return f(n - 1, heights);
    }

    static int f(int ind, int[] a) {
        if (ind == 0) {
            return 0;
        }

        int l = f(ind - 1, a) + Math.abs(a[ind] - a[ind - 1]);
        int right = Integer.MAX_VALUE;

        if (ind > 1) {
            right = f(ind - 2, a) + Math.abs(a[ind] - a[ind - 2]);
        }

        return Math.min(l, right);
    }
}

However, this recursive solution has exponential time complexity, making it inefficient for large inputs. To optimize the solution, we turn to dynamic programming.

Dynamic Programming Solution

Dynamic programming allows us to avoid redundant calculations by storing the results of subproblems in a table. We create an array dp to memoize the minimum cost at each step. The iterative solution uses a loop to fill in the table.

int frogJump(int n, vector<int> &heights) {
    vector<int> dp(n, -1);
// Base case
    dp[0] = 0;
    for (int i = 1; i < n; ++i) {
        int fs = dp[i - 1] + abs(heights[i] - heights[i - 1]);
        int ss = INT_MAX;
        if (i > 1) {
            ss = dp[i - 2] + abs(heights[i] - heights[i - 2]);
        }
        dp[i] = min(fs, ss);
    }
    return dp[n - 1];
}

import java.util.Arrays;

public class Solution {
    public static int frogJump(int n, int heights[]) {
        int[] dp = new int[n];
        Arrays.fill(dp, -1);

        // Base case
        dp[0] = 0;

        for (int i = 1; i < n; ++i) {
            int fs = dp[i - 1] + Math.abs(heights[i] - heights[i - 1]);
            int ss = Integer.MAX_VALUE;

            if (i > 1) {
                ss = dp[i - 2] + Math.abs(heights[i] - heights[i - 2]);
            }

            dp[i] = Math.min(fs, ss);
        }

        return dp[n - 1];
    }
}

This dynamic programming solution has a time complexity of O(n), making it much more efficient than the recursive approach.

Conclusion

The Frog Jumping Problem is a classic example that demonstrates the power of dynamic programming in optimizing solutions to certain types of problems. By breaking down the problem into smaller subproblems and memoizing the results, we can achieve significant time complexity improvements. The iterative dynamic programming solution in C++ provides a practical implementation that can handle larger inputs efficiently.

In real-world scenarios, understanding the principles behind dynamic programming enables programmers to design efficient algorithms for various optimization problems. The Frog Jumping Problem serves as an excellent introduction to these concepts, showcasing how a seemingly complex problem can be elegantly solved through dynamic programming techniques.

check out the problem https://www.codingninjas.com/studio/problems/frog-jump_3621012?leftPanelTabValue=PROBLEM&count=25&page=2&search=&difficulty%5B%5D=Ninja&sort_entity=order&sort_order=ASC

connect with me https://www.linkedin.com/in/roshan-jha-20m10/