PROBLEM LINK:
Author: Ram Agrawal
Tester: Ram Agrawal
Editorialist: Ram Agrawal
DIFFICULTY:
EASY-MEDIUM,
PREREQUISITES:
dynamic-programming
PROBLEM:
he cat wants to Climb some stairs from the 0th stair to the (N-1)th stair. Given the number of stairs NN and the height of each stair. The cat is allowed to jump up to ‘K’ steps at a time. If K=4, the cat can jump 1,2,3, or 4 steps at every index. A height[N] array is also given. Whenever the cat jumps from a stair i to stair j, the energy consumed in the jump is abs(height[i]- height[j]), where abs() means the absolute difference.
We need to determine the minimum energy that can be used by the cat to jump from stair 0 to stair N-1.
QUICK EXPLANATION:
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).
EXPLANATION:
the cat was allowed to jump either one or two steps at a time. In this question, the cat is allowed to jump up to ‘K’ steps at a time. If K=4, the cat can jump 1,2,3, or 4 steps at every index.
Memoization approach
- 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.
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).
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int func(int i,int k,int dp[],int h[]){
if(i==0)return 0;
if(dp[i]!=-1)return dp[i];
int cost=INT_MAX;
for(int j=1;j<=k;j++){
if(i-j >=0)
cost=min(cost,func(i-j,k,dp,h)+abs(h[i]-h[i-j]));
}
return dp[i]=cost;
}
int main() {
// your code goes here
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
int j=0;
int a[n];
while(j<n)cin>>a[j++];
int dp[n+1];
memset(dp,-1,sizeof(dp));
cout<<func(n-1,k,dp,a)<<endl;
// your code goes here
}
return 0;
}
Tester's Solution
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
while(t-->0){
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
ArrayList<Integer> al = new ArrayList<>();
for(int i = 0;i<n;i++){
al.add(Integer.parseInt(st.nextToken()));
}
int[] dp = new int[n];
dp[0] =0;
for(int i = 1;i<n;i++){
int min = Integer.MAX_VALUE;
for(int j = i-k;j<i;j++){
if(j<0){
continue;
}
min = Math.min(min,dp[j]+Math.abs(al.get(i)-al.get(j)));
}
dp[i] = min;
}
bw.write(dp[n-1]+"\n");
}
bw.flush();
}
}
Editorialist's Solution
import math, bisect, heapq, random, sys, itertools
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
ints = lambda : list(map(int,input().split()))
p = 10**9+7
for t in range(int(input())):
n,k = ints()
a = ints()
dp = [p]*(n+1)
dp[0] = 0
for i in range(n):
for j in range(i+1,min(n,i+k+1)):
dp[j] = min(dp[j],dp[i]+abs(a[i]-a[j]))
print(dp[n-1])