In this article, we will learn about “Dynamic Programming: Frog Jump with k Distances (DP 4)”
Problem Statement: Frog Jump with K Distance/ Learn to write 1D DP
Problem Statement:
This is a follow-up question to “Frog Jump” discussed in the previous article. In the previous question, the frog was allowed to jump either one or two steps at a time. In this question, the frog is allowed to jump up to ‘K’ steps at a time. If K=4, the frog can jump 1,2,3, or 4 steps at every index.
Pre-req: Frog Jump
Practice:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Memorization Approach
Algorithm / Intuition
We will first see the modifications required in the pseudo-code. Once the recursive code is formed, we can go ahead with the memorization and tabulation.
Here is the pseudocode from the simple Frog Jump problem.
This was the case where we needed to try two options (move a single step and move two steps) in order to try out all the possible ways for the problem. Now, we need to try K options in order to try out all possible ways.
These are the calls we need to make for K=2, K=3, K=4
If we generalize, we are making K calls, therefore, we can set a for loop to run from 1 to K, and in each iteration, we can make a function call, corresponding to a step. We will return the minimum step call after the loop.
The final pseudo-code will be:
Note: We need to make sure that we are not passing negative index to the array, therefore an extra if the condition is used.
Once we form the recursive solution, we can use the approach told in Dynamic Programming Introduction to convert it into a dynamic programming one.
Memoization approach
Steps to convert Recursive code to memoization solution:
- Create a dp[n] array initialized to -1.
- Whenever we want to find the answer of a particular value (say n), we first check whether the answer is already calculated using the dp array(i.e dp[n] != -1 ). If yes, simply return the value from the dp array.
- If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[n] to the solution we get.
Code
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost to reach the end using at most 'k' jumps
int solveUtil(int ind, vector<int>& height, vector<int>& dp, int k) {
// Base case: If we are at the beginning (index 0), no cost is needed.
if (ind == 0) return 0;
// If the result for this index has been previously calculated, return it.
if (dp[ind] != -1) return dp[ind];
int mmSteps = INT_MAX;
// Loop to try all possible jumps from '1' to 'k'
for (int j = 1; j <= k; j++) {
// Ensure that we do not jump beyond the beginning of the array
if (ind - j >= 0) {
// Calculate the cost for this jump and update mmSteps with the minimum cost
int jump = solveUtil(ind - j, height, dp, k) + abs(height[ind] - height[ind - j]);
mmSteps = min(jump, mmSteps);
}
}
// Store the minimum cost for this index in the dp array and return it.
return dp[ind] = mmSteps;
}
// Function to find the minimum cost to reach the end of the array
int solve(int n, vector<int>& height, int k) {
vector<int> dp(n, -1); // Initialize a memoization array to store calculated results
return solveUtil(n - 1, height, dp, k); // Start the recursion from the last index
}
int main() {
vector<int> height{30, 10, 60, 10, 60, 50};
int n = height.size();
int k = 2;
vector<int> dp(n, -1); // Initialize a memoization array for the main function
cout << solve(n, height, k) << endl; // Print the result of the solve function
return 0;
}
import java.util.*;
class TUF {
// Recursive function to calculate the minimum cost to reach the end
// from a given index with at most 'k' jumps.
static int solveUtil(int ind, int[] height, int[] dp, int k) {
// Base case: If we are at the beginning (index 0), no cost is needed.
if (ind == 0)
return 0;
// If the result for this index has been previously calculated, return it.
if (dp[ind] != -1)
return dp[ind];
int mmSteps = Integer.MAX_VALUE;
// Loop to try all possible jumps from '1' to 'k'
for (int j = 1; j <= k; j++) {
// Ensure that we do not jump beyond the beginning of the array
if (ind - j >= 0) {
// Calculate the cost for this jump and update mmSteps with the minimum cost
int jump = solveUtil(ind - j, height, dp, k) + Math.abs(height[ind] - height[ind - j]);
mmSteps = Math.min(jump, mmSteps);
}
}
// Store the minimum cost for this index in the dp array and return it.
return dp[ind] = mmSteps;
}
// Function to find the minimum cost to reach the end of the array
static int solve(int n, int[] height, int k) {
int[] dp = new int[n];
Arrays.fill(dp, -1); // Initialize a memoization array to store calculated results
return solveUtil(n - 1, height, dp, k); // Start the recursion from the last index
}
public static void main(String args[]) {
int height[] = { 30, 10, 60, 10, 60, 50 };
int n = height.length;
int k = 2;
System.out.println(solve(n, height, k)); // Print the result of the solve function
}
}
import sys
# Recursive function to calculate the minimum cost to reach the end
# from a given index with at most 'k' jumps.
def solveUtil(ind, height, dp, k):
# Base case: If we are at the beginning (index 0), no cost is needed.
if ind == 0:
return 0
# If the result for this index has been previously calculated, return it.
if dp[ind] != -1:
return dp[ind]
mmSteps = sys.maxsize
# Loop to try all possible jumps from '1' to 'k'
for j in range(1, k + 1):
# Ensure that we do not jump beyond the beginning of the array
if ind - j >= 0:
# Calculate the cost for this jump and update mmSteps with the minimum cost
jump = solveUtil(ind - j, height, dp, k) + abs(height[ind] - height[ind - j])
mmSteps = min(jump, mmSteps)
# Store the minimum cost for this index in the dp array and return it.
dp[ind] = mmSteps
return dp[ind]
# Function to find the minimum cost to reach the end of the array
def solve(n, height, k):
dp = [-1] * n # Initialize a memoization array to store calculated results
return solveUtil(n - 1, height, dp, k) # Start the recursion from the last index
def main():
height = [30, 10, 60, 10, 60, 50]
n = len(height)
k = 2
print(solve(n, height, k)) # Print the result of the solve function
if __name__ == "__main__":
main()
function solveUtil(ind, height, dp, k) {
// Base case: If we are at the beginning (index 0), no cost is needed.
if (ind === 0) return 0;
// If the result for this index has been previously calculated, return it.
if (dp[ind] !== -1) return dp[ind];
let mmSteps = Infinity;
// Loop to try all possible jumps from '1' to 'k'
for (let j = 1; j <= k; j++) {
// Ensure that we do not jump beyond the beginning of the array
if (ind - j >= 0) {
// Calculate the cost for this jump and update mmSteps with the minimum cost
const jump =
solveUtil(ind - j, height, dp, k) + Math.abs(height[ind] - height[ind - j]);
mmSteps = Math.min(jump, mmSteps);
}
}
// Store the minimum cost for this index in the dp array and return it.
dp[ind] = mmSteps;
return dp[ind];
}
function solve(n, height, k) {
const dp = Array(n).fill(-1); // Initialize a memoization array to store calculated results
return solveUtil(n - 1, height, dp, k); // Start the recursion from the last index
}
const height = [30, 10, 60, 10, 60, 50];
const n = height.length;
const k = 2;
const dp = Array(n).fill(-1); // Initialize a memoization array for the main function
console.log(solve(n, height, k)); // Print the result of the solve function
Output: 40
Complexity Analysis
Time Complexity: O(N *K)
Reason: The overlapping subproblems will return the answer in constant time. Therefore the total number of new subproblems we solve is ‘n’. At every new subproblem, we are running another loop for K times. Hence total time complexity is O(N * K).
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N)) and an array (again O(N)). Therefore total space complexity will be O(N) + O(N) ≈ O(N)
Tabulation Approach
Algorithm / Intuition
Tabulation approach
- Declare a dp[] array of size n.
- First initialize the base condition values, i.e dp[0] as 0.
- Set an iterative loop which traverses the array( from index 1 to n-1) and for every index calculate jumpOne and jumpTwo and set dp[i] = min(jumpOne, jumpTwo).
Code
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost to reach the end using at most 'k' jumps
int solveUtil(int n, vector<int>& height, vector<int>& dp, int k) {
dp[0] = 0;
// Loop through the array to fill in the dp array
for (int i = 1; i < n; i++) {
int mmSteps = INT_MAX;
// Loop to try all possible jumps from '1' to 'k'
for (int j = 1; j <= k; j++) {
if (i - j >= 0) {
int jump = dp[i - j] + abs(height[i] - height[i - j]);
mmSteps = min(jump, mmSteps);
}
}
dp[i] = mmSteps;
}
return dp[n - 1]; // The result is stored in the last element of dp
}
// Function to find the minimum cost to reach the end of the array
int solve(int n, vector<int>& height, int k) {
vector<int> dp(n, -1); // Initialize a memoization array to store calculated results
return solveUtil(n, height, dp, k);
}
int main() {
vector<int> height{30, 10, 60, 10, 60, 50};
int n = height.size();
int k = 2;
vector<int> dp(n, -1); // Initialize a memoization array for the main function
cout << solve(n, height, k) << endl; // Print the result of the solve function
return 0;
}
import java.util.*;
class TUF {
// Function to find the minimum cost to reach the end using at most 'k' jumps
static int solveUtil(int n, int[] height, int[] dp, int k) {
dp[0] = 0;
// Loop through the array to fill in the dp array
for (int i = 1; i < n; i++) {
int mmSteps = Integer.MAX_VALUE;
// Loop to try all possible jumps from '1' to 'k'
for (int j = 1; j <= k; j++) {
if (i - j >= 0) {
int jump = dp[i - j] + Math.abs(height[i] - height[i - j]);
mmSteps = Math.min(jump, mmSteps);
}
}
dp[i] = mmSteps;
}
return dp[n - 1]; // The result is stored in the last element of dp
}
// Function to find the minimum cost to reach the end of the array
static int solve(int n, int[] height, int k) {
int[] dp = new int[n]; // Initialize a memoization array to store calculated results
Arrays.fill(dp, -1);
return solveUtil(n, height, dp, k);
}
public static void main(String args[]) {
int height[] = {30, 10, 60, 10, 60, 50};
int n = height.length;
int k = 2;
System.out.println(solve(n, height, k)); // Print the result of the solve function
}
}
import sys
# Helper function to solve the problem using dynamic programming
def solve_util(n, height, dp, k):
# Initialize the first element of the dp array as 0 since no steps are needed to reach the first position
dp[0] = 0
# Loop through the elements of the height array
for i in range(1, n):
mmSteps = sys.maxsize # Initialize the minimum steps to a large value
for j in range(1, k+1):
if i - j >= 0:
# Calculate the number of steps required to reach the current position from the previous positions
jump = dp[i - j] + abs(height[i] - height[i - j])
mmSteps = min(jump, mmSteps) # Update the minimum steps
dp[i] = mmSteps # Store the minimum steps needed to reach the current position
return dp[n-1] # Return the minimum steps needed to reach the last position
# Main function to solve the problem
def solve(n, height, k):
dp = [-sys.maxsize] * n # Initialize a dp array with large negative values
return solve_util(n, height, dp, k) # Call the helper function
# Entry point of the program
def main():
height = [30, 10, 60, 10, 60, 50]
n = len(height)
k = 2
dp = [-sys.maxsize] * n # Initialize dp array
result = solve(n, height, k) # Call the solve function
print(result) # Print the result
if __name__ == "__main__":
main()
// Define the solveUtil function to calculate the minimum steps required
function solveUtil(n, height, dp, k) {
// Initialize the first element in dp to 0
dp[0] = 0;
// Loop through the height array from index 1 to n-1
for (let i = 1; i < n; i++) {
// Initialize mmSteps to a large value
let mmSteps = Infinity;
// Loop through the last k elements (backward jumps)
for (let j = 1; j <= k; j++) {
// Check if it's possible to jump to the previous element
if (i - j >= 0) {
// Calculate the cost of the jump and update mmSteps with the minimum cost
const jump = dp[i - j] + Math.abs(height[i] - height[i - j]);
mmSteps = Math.min(jump, mmSteps);
}
}
// Store the minimum cost in dp for the current index
dp[i] = mmSteps;
}
// Return the minimum cost to reach the last element
return dp[n - 1];
}
// Define the solve function to initialize dp and call solveUtil
function solve(n, height, k) {
// Initialize the dp array with -1
const dp = new Array(n).fill(-1);
// Call solveUtil to calculate the minimum cost
return solveUtil(n, height, dp, k);
}
// Main function
function main() {
// Input height array
const height = [30, 10, 60, 10, 60, 50];
// Calculate the length of the height array
const n = height.length;
// Set the maximum allowed jumps (k)
const k = 2;
// Initialize the dp array with -1
const dp = new Array(n).fill(-1);
// Call the solve function and print the result
console.log(solve(n, height, k));
}
// Call the main function to start the program
main();
Output: 40
Complexity Analysis
Time Complexity: O(N*K)
Reason: We are running two nested loops, where outer loops run from 1 to n-1 and the inner loop runs from 1 to K
Space Complexity: O(N)
Reason: We are using an external array of size ‘n’’.
Video Explanation
Special thanks to Anshuman Sharma and Abhipsita Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article