In this thread we will see how a single dynamic programming (DP) approach can be adapted to solve multiple seemingly different problems. By understanding the core pattern, we can efficiently tackle a wide range of algorithmic challenges.

Here's why this is valuable:

Pattern Recognition:

The problems discussed here (Climbing Stairs, Min Cost Climbing Stairs, House Robber, and House Robber II) all involve making optimal decisions at each step while considering constraints (e.g., no two adjacent steps/houses).

Reusable Framework

The recursive + memoization approach provides a reusable framework for solving DP problems.

Once you understand the base cases, recursive relation, and memoization, you can apply it to new problems with minimal adjustments.

1. Climbing Stairs
2. Min Cost Climbing Stairs
3. House Robber
4. House Robber II,

All these can be solved using a similar dynamic programming approach. The core idea is to break down the problem into smaller subproblems and use memoization to avoid redundant calculations.

Common Pattern:

1. Base Cases: Handle the smallest subproblems directly.
2. Recursive Case: Define the problem in terms of smaller subproblems.
3. Memoization: Store the results of subproblems to avoid redundant calculations.

Climbing Stairs

Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

climbStairs(n) {
   if(n === 0 ){
     return  0
    }
    
   if(n === 1){
      return 1
   }

   if(n === 2){
     return 2
   }
    
  if(this.map.has(n)){
       return this.map.get(n)
  }

 const result = this.climbStairs(n-1) + this.climbStairs(n-2)
 this.map.set(n, result)
        
 return result
 }
}

Min Cost Climbing Stairs

Problem: You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can start from either step 0 or step 1. Return the minimum cost to reach the top of the floor.

minCostClimbingStairs(cost) {
    const map = new Map();

    return Math.min(
      helper(cost.length - 1),
      helper(cost.length - 2)
    );
}

function helper(step) {
      if (step < 0) {
        return 0;
      }
      if (step === 0) {
        return cost[0];
      }
      if (step === 1) {
        return cost[1];
      }
      if (map.has(step)) {
        return map.get(step);
      }
      const min = Math.min(
        cost[step] + helper(step - 2),
        cost[step] + helper(step - 1)
      );
      map.set(step, min);
      return min;
}

House Robber

Problem: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

rob(nums)
  return this.helper(nums, nums.length - 1)
}

helper(amount, house) {

if (house < 0) {
   return 0
}
  
if(house === 0){
  return amount[0]
}

if (house === 1) {
  return Math.max(amount[0], amount[1])
}

if (this.map.has(house)) {
 return this.map.get(house)
}

const max = Math.max(
  amount[house] + this.helper(amount, house - 2),
  this.helper(amount, house - 1)
 )

this.map.set(house, max)
return max

}

House Robber II

Problem: This is a variation of the House Robber problem where the houses are arranged in a circle. That means the first house is the neighbor of the last one.

 rob(nums) {
        return Math.max(
            this.robRange(nums, 0, nums.length -2),
            this.robRange(nums, 1, nums.length -1)
        )
}

robRange(amounts, start, end) {
  const map = new Map()
  return helper(end)
}

  function helper(house) {
     if (house < 0) {
        return 0
     }

    if (house === start) {
      return amounts[start]
     }

    if (house === start +1) {
      return Math.max(amounts[start], amounts[start + 1])
     }

    if (map.has(house)) {
      return map.get(house)
     }
    
   const max = Math.max(
                amounts[house] + helper(house - 2),
                helper(house - 1)
    )
           
   map.set(house, max)
   return max
   }

• Climbing Stairs: The number of ways to reach the top is the sum of the ways to reach the (n-1)th step and the (n-2)th step.
• Min Cost Climbing Stairs: The minimum cost to reach the top is the minimum of the cost to reach the (n-1)th step and the (n-2)th step, plus the current step's cost.
• House Robber: The maximum amount of money you can rob is the maximum of robbing the current house and skipping the previous one, or skipping the current house.
• House Robber II: The same as House Robber, but you need to consider two scenarios: one where you rob the first house and skip the last, and another where you skip the first and rob the last.

Here are some more problems that can be solved using the same DP approach:

1. Fibonacci Number:

• Calculate the nth Fibonacci number using recursion and memoization.

1. Maximum Subarray Sum:

• Find the contiguous subarray with the largest sum.

1. Coin Change:

• Determine the minimum number of coins needed to make a certain amount.

1. Longest Increasing Subsequence:

• Find the length of the longest subsequence of a given sequence such that all elements are in increasing order.

1. Decode Ways:

• Given a string of digits, determine the number of ways to decode it into letters (A=1, B=2, ..., Z=26).

1. Unique Paths:

• Find the number of unique paths in a grid from the top-left corner to the bottom-right corner, moving only right or down.

#dynamicProgramming #leetcode #houserobber #minStairCase