Climbing Stairs

Given an integer n, there is a staircase with n steps, starting from the 0th step. Determine the number of unique ways to reach the nth step, given that each move can be either 1 or 2 steps at a time.

// Memoization

class Solution
{
public:
    int func(vector<int> &dp, int n)
    {
        if (n <= 1)
            return 1;
        if (dp[n] != -1)
            return dp[n];

        return dp[n] = func(dp, n - 1) + func(dp, n - 2);
    }
    int climbStairs(int n)
    {
        vector<int> dp(n + 1, -1);

        return func(dp, n);
    }
};

// Tabulation

class Solution2
{
public:
    int climbStairs(int n)
    {
        vector<int> dp(n + 1, -1);

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

Frog Jump

A frog wants to climb a staircase with n steps. Given an integer array heights, where heights[i] contains the height of the ith step. To jump from the ith step to the jth step, the frog requires abs(heights[i] - heights[j]) energy, where abs() denotes the absolute difference. The frog can jump from any step either one or two steps, provided it exists. Return the minimum amount of energy required by the frog to go from the 0th step to the (n-1)th step.

// Memoization
class Solution
{
public:
    int func(vector<int> &heights, int i, vector<int> &dp)
    {
        if (i <= 0)
            return 0;
        if (dp[i] != -1)
            return dp[i];
        //take 1 step
        int oneStep = func(heights, i - 1, dp) + abs(heights[i] - heights[i - 1]);
        //take 2 step
        int twoStep = INT_MAX;
        if (i > 1) // to avoid negative indexing
        {
            twoStep = func(heights, i - 2, dp) + abs(heights[i] - heights[i - 2]);
        }
        return dp[i] = min(oneStep, twoStep);
    }
    int frogJump(vector<int> &heights)
    {
        int n = heights.size();
        //size n because we have to reach the (n-1)th step
        vector<int> dp(n, -1);
        return func(heights, n - 1, dp);
    }
};

// Tabulation

class Solution {
public:
    int frogJump(vector<int>& heights) {
        int n = heights.size();
        vector<int>dp(n,-1);
        dp[0]=0;
        for(int i=1;i<n;i++){
            int oneStep = dp[i-1]+abs(heights[i]-heights[i-1]);
            int twoStep=INT_MAX;
            if(i>1) twoStep = dp[i-2]+abs(heights[i]-heights[i-2]);
            dp[i] = min(oneStep,twoStep);
        }
        return dp[n-1];
    }
};

// Space Optimization

class Solution {
public:
    int frogJump(vector<int>& heights) {
        int n = heights.size();
        int prev=0;
        int prev2 = 0;
        for(int i=1;i<n;i++){
            int oneStep = prev+abs(heights[i]-heights[i-1]);
            int twoStep=INT_MAX;
            if(i>1) twoStep = prev2+abs(heights[i]-heights[i-2]);
            int curri = min(oneStep,twoStep);
            prev2=prev;
            prev=curri;
        }
        return prev;
    }
};

House Robber

A robber is targeting to rob houses from a street. Each house has security measures that alert the police when two adjacent houses are robbed. The houses are arranged in a circular manner, thus the first and last houses are adjacent to each other.

Given an integer array money, where money[i] represents the amount of money that can be looted from the (i+1)th house. Return the maximum amount of money that the robber can loot without alerting the police.

 int func(int i, vector<int> &nums, vector<int> &dp)
    {
        if (i < 0)
            return 0;
        if (i == 0)
            return nums[i];
        if (dp[i] != -1)
            return dp[i];

        int pick = nums[i] + func(i - 2, nums, dp);
        int dontPick = func(i - 1, nums, dp);

        return dp[i] = max(pick, dontPick);
    }
    int houseRobber(vector<int> &money)
    {
        int n = money.size();
        if (n == 1)
            return money[0];
        vector<int> withoutFirst, withoutLast;
        vector<int> dp1(n, -1);
        vector<int> dp2(n, -1);
        for (int i = 0; i < n; i++)
        {
            if (i != n - 1)
                withoutLast.push_back(money[i]);
            if (i != 0)
                withoutFirst.push_back(money[i]);
        }
        int ans1 = func(withoutFirst.size() - 1, withoutFirst, dp1);
        int ans2 = func(withoutLast.size() - 1, withoutLast, dp2);

        return max(ans1, ans2);
    }