title: 'DP problem set-1'
topic : 'dynamic-programming'
id: 1
description: 'Dynamic programming problem set of 1D dp. problems - climbing stairs and frog jump'
subtopic: ['1d-dp']
DP problem set -1
Summary for the blog β¨οΈβ¨οΈ
In this blog of Dynamic programming, we will discuss basic DP problems, we will see the problem solving approach, intuition and the code solution for the problems.
we can think the problem of in a quite reverse way! think that we are at the nth stair. how do I reach there? either through n-1th stair or n-2th stair.
Hence we can think of solving the problem in a recursive way, at each stair we will explore the possibility of either jumping 1 step or 2 step backwards.
The base case would be if we reach stair 0 we would return 1, else if the stair reached is less than 0, we would return 0,
Since the time complexity is 2^n and space complexity if O(n), we would need to optimize it, we will use a technique called memoisation to optimize it.
you can explore other technique called tabulation as well.
This is similar to the previous problem, we will start from the nth stair and go to 1st stair.
Its given that for jumping from ith stair to jth stair, energy used is absolute value of height[i-1] + height[j-1].
The base case would be if we reach stair 1 we would return 0 (as no more energy is needed to reach the destination), else if the stair reached is less than 1, we would return a large value like 1e9, as this will not be our answer, returning a large value will exclude this answer ( do not return INT_MAX as it would overflow while adding with other integers).
We would explore the possibility of going 1 step and 2 step backwards, and return the minimum among them.
Since the time complexity is 2^n and space complexity if O(n), we would need to optimize it, we will use a technique called memoisation to optimize it.
you can explore other technique called tabulation as well.
#include<iostream>#include<bits/stdc++.h>intsolve(int n, vector<int>&heights,vector<int>&dp){if(n==1){return0;}if(dp[n]!=-1){return dp[n];}int first=solve(n-1,heights,dp)+abs(heights[n-1]-heights[n-2]);int second=INT_MAX;if(n>2){ second=solve(n-2,heights,dp)+abs(heights[n-1]-heights[n-3]);} dp[n]=min(first,second);returnmin(first,second);}intfrogJump(int n, vector<int>&heights){// Write your code here. vector<int>dp(n+1,-1);int ans =solve(n,heights,dp);return ans;}
Follow up of problem No - 2
Intuition :-
This is similar to the previous problem, we will start from the nth stair and go to 1st stair.
Its given that for jumping from ith stair to jth stair, energy used is absolute value of height[i-1] + height[j-1].
The base case would be if we reach stair 1 we would return 0 (as no more energy is needed to reach the destination), else if the stair reached is less than 1, we would return a large value like 1e9, as this will not be our answer, returning a large value will exclude this answer ( do not return INT_MAX as it would overflow while adding with other integers).
We would explore the possibility of going 1 step and 2 step backwards, and return the minimum among them.
Since the time complexity is 2^n and space complexity if O(n), we would need to optimize it, we will use a technique called memoisation to optimize it.
you can explore other technique called tabulation as well.
#include<iostream>#include<bits/stdc++.h>intsolve(int n, vector<int>&heights,vector<int>&dp){if(n==1){return0;}if(dp[n]!=-1){return dp[n];}int minEnergy =INT_MAX;for(int j=1;j<=k;j++){int energy = INT_MAX;if(j+1>=0) energy =solve(n-j,heights,dp)+abs(heights[n-1]-heights[n-j-1]); minEnergy =min(minEnergy,energy);} dp[n]=min(first,second);returnmin(first,second);}intfrogJump(int n, vector<int>&heights,int k){// Write your code here. vector<int>dp(n+1,-1);int ans =solve(n,heights,dp,k);return ans;}
: Hey! is your brain fried of this blog? . Well what about a game with me?