Daily Code by Nirbhay
Frog Jump

Frog Jump

Nirbhay Singh's photo
Nirbhay Singh
·

2 min read

Table of contents

Frog Jump - 1D Dynamic Programming

My approach:

As I observed that we cannot use a greedy approach to solve this problem. We need to try out all the possibilities to find the solution.

To find all possibilities, we use Recursion and with the help of memoization, we can optimize the solution.

Instead of a top-down approach, we should always think about the bottom-up approach which is the dynamic programming solution.

My solution:

  • Recursive

image1

  • Iterative

image2

Code:

  • Recursion with Memoization

#include <bits/stdc++.h>
int helper(int n,int s, vector<int> &heights, vector<int> &dp) {

    if(s>=n){
        return 0;
    }

    if(dp[s]!=-1){
        return dp[s];
    }

    int a = 0;
    int b = INT_MAX;

    if(s+1<n){
        a = helper(n,s+1, heights,dp) + abs(heights[s]-heights[s+1]);
    }
    if(s+2<n){
        b = helper(n,s+2,heights,dp) + abs(heights[s]-heights[s+2]);
    }

    dp[s] = min(a,b);
    return min(a,b);
}
int frogJump(int n, vector<int> &heights)
{
    vector<int> dp(n,-1);
    return helper(n,0,heights,dp);
}

int frogJump(int n, vector<int> &heights)
{
    vector<int> dp(n);

    dp[0] = 0;
    dp[1] = abs(heights[0]-heights[1]);
    dp[2] = abs(heights[0]-heights[2]);

    for(int i=3;i<n;i++){
        int a = abs(heights[i]-heights[i-1])+dp[i-1];
        int b = abs(heights[i]-heights[i-2])+dp[i-2];

        dp[i] = min(a,b);
    }

    return dp[n-1];

}

  • Dynamic Programming

#include <bits/stdc++.h>
int frogJump(int n, vector<int> &heights)
{
    vector<int> dp(n);

    dp[0] = 0;
    dp[1] = abs(heights[0]-heights[1]);

    for(int i=2;i<n;i++){
        int a = abs(heights[i]-heights[i-1])+dp[i-1];
        int b = abs(heights[i]-heights[i-2])+dp[i-2];

        dp[i] = min(a,b);
    }

    return dp[n-1];
}

https://www.codingninjas.com/studio/problems/frog-jump_3621012

Dynamic ProgrammingDSAcodingC++