---

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.

Sl No	Leetcode problems/ Algorithms	Link
1	Climbing Stairs	Problem 1
2	Frog Jump	Problem 1

Problem No - 1

Intuition :-

• 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.

class Solution {
public:
    int solve(int nStairs, vector<int>& dp) {
        if (nStairs == 0 || nStairs == 1) {
            return 1;
        }

        if (dp[nStairs] != -1) {
            return dp[nStairs];
        }
        int a = solve(nStairs - 2, dp) + solve(nStairs - 1, dp);
        dp[nStairs] = a;
        return a;
    }
    int climbStairs(int n) {
        vector<int> dp(n+2,-1);
        int ans = solve(n, dp);
        return ans;
    }
};

---

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> 
int solve(int n, vector<int> &heights,vector<int>&dp){
    if(n==1){
        return 0;
    }
    
    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);
    return min(first,second);
}
int frogJump(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> 
int solve(int n, vector<int> &heights,vector<int>&dp){
    if(n==1){
        return 0;
    }
    
    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);
    return min(first,second);
}
int frogJump(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;
}

---