Rocket Academy Bootcamp
  • 🚀Welcome to Bootcamp!
  • 🛠️Logistics
    • Course Schedules
    • Course Methodology
    • Required Software
    • LinkedIn Education Badge
  • 📚General Reference
    • Naming, Casing, and Commenting Conventions
    • VS Code Tips
    • Recommended Resources
  • 🪨0: Foundations
    • 0.1: Command Line
    • 0.2: Git
      • 0.2.1: Branches
    • 0.3: GitHub
      • 0.3.1: Pull Requests
    • 0.4: JavaScript
      • 0.4.1: ES6
      • 0.4.2: Common Syntax
      • 0.4.3: Reference vs Value
      • 0.4.4: Classes
      • 0.4.5: Destructuring and Spread Operator
      • 0.4.6: Promises
        • 0.4.6.1: Async Await
    • 0.5: Node.js
      • 0.5.1: Node Modules
      • 0.5.2: NPM
      • 0.5.3: Nodemon
  • 🖼️1: Frontend
    • 1.1: HTML
    • 1.2: CSS
      • 1.2.1: Layout
    • 1.3: React
      • Styling in ReactJs
      • Using Styling Libraries with React
      • React Deployment
    • 1.E: Exercises
      • 1.E.1: Recipe Site
      • 1.E.2: Portfolio Page
      • 1.E.3: World Clock
      • 1.E.4: High Card
      • 1.E.5: Guess The Word
    • 1.P: Frontend App
  • 🏭2: Full Stack
    • 2.1: Internet 101
      • 2.1.1: Chrome DevTools Network Panel
      • 2.1.2: HTTP Requests and Responses
    • 2.2: Advanced React
      • 2.2.1: AJAX
      • 2.2.2: React Router
      • 2.2.3: useContext
      • 2.2.4: useReducer
      • 2.2.5: Environmental Variables
      • 2.2.6: React useMemo - useCallback
    • 2.3: Firebase
      • 2.3.1: Firebase Realtime Database
      • 2.3.2: Firebase Storage
      • 2.3.3: Firebase Authentication
      • 2.3.4: Firebase Hosting
      • 2.3.5: Firebase Techniques
    • 2.E: Exercises
      • 2.E.1: Weather App
      • 2.E.2: Instagram Chat
      • 2.E.3: Instagram Posts
      • 2.E.4: Instagram Auth
      • 2.E.5: Instagram Routes
    • 2.P: Full-Stack App (Firebase)
  • 🤖3: Backend
    • 3.1: Express.js
      • 3.1.1 : MVC
    • 3.2: SQL
      • 3.2.1: SQL 1-M Relationships
      • 3.2.2: SQL M-M Relationships
      • 3.2.3: SQL Schema Design
      • 3.2.4: Advanced SQL Concepts
      • 3.2.5: SQL - Express
      • 3.2.6: DBeaver
    • 3.3: Sequelize
      • 3.3.1: Sequelize One-To-Many (1-M) Relationships
      • 3.3.2: Sequelize Many-To-Many (M-M) Relationships
      • 3.3.3: Advanced Sequelize Concepts
      • 3.3.4 Database Design
    • 3.4: Authentication
      • 3.4.1: JWT App
    • 3.5: Application Deployment
    • 3.E: Exercises
      • 3.E.1: Bigfoot JSON
      • 3.E.2: Bigfoot SQL
      • 3.E.3: Bigfoot SQL 1-M
      • 3.E.4: Bigfoot SQL M-M
      • 3.E.5: Carousell Schema Design
      • 3.E.6: Carousell Auth
    • 3.P: Full-Stack App (Express)
  • 🏞️4: Capstone
    • 4.1: Testing
      • 4.1.1: Frontend React Testing
      • 4.1.2: Backend Expressjs Testing
    • 4.2: Continuous Integration
      • 4.2.1 Continuous Deployment (Fly.io)
      • 4.2.2: Circle Ci
    • 4.3: TypeScript
    • 4.4: Security
    • 4.5: ChatGPT for SWE
    • 4.6: Soft Skills for SWE
    • 4.P: Capstone
  • 🧮Algorithms
    • A.1: Data Structures
      • A.1.1: Arrays
        • A.1.1.1: Binary Search
        • A.1.1.2: Sliding Windows
      • A.1.2: Hash Tables
      • A.1.3: Stacks
      • A.1.4: Queues
      • A.1.5: Linked Lists
      • A.1.6: Trees
      • A.1.7: Graphs
      • A.1.8: Heaps
    • A.2: Complexity Analysis
    • A.3: Object-Oriented Programming
    • A.4: Recursion
    • A.5: Dynamic Programming
    • A.6: Bit Manipulation
    • A.7: Python
  • 💼Interview Prep
    • IP.1: Job Application Strategy
    • IP.2: Resume
    • IP.3: Portfolio
Powered by GitBook
On this page
  • Learning Objectives
  • Introduction
  • Take or Don't Take
  • Exercises
  • Part 1
  • Part 2
  • Part 3
  • Part 4
  • More Comfortable
  • Further Reading
  1. Algorithms

A.5: Dynamic Programming

PreviousA.4: RecursionNextA.6: Bit Manipulation

Learning Objectives

  1. Dynamic programming (DP) problems are a subset of recursion problems that involve caching intermediate calculations to avoid repeated calculations

  2. DP problems often involve "take or don't take" logic in each recursive call, which results in repeated calculations without caching

  3. DP problems are not the most commonly seen interview problems (less common at most SWE jobs), and Rocket recommends being comfortable with prior algorithm topics before spending too much time on DP

Introduction

Dynamic programming allows us to optimise recursive solutions by "caching" (i.e. storing) intermediate calculations to minimise repeated and redundant recursive calls.

The first 40 minutes of the below video visually explain the premise behind dynamic programming and why it is powerful. The remainder of the video walks through DP solutions to other problems, which we do not need to review right now.

Take or Don't Take

Many dynamic programming problems involve "take or don't take" logic, where we will need to choose an optimal set of values from a collection (e.g. array) with constraints such as no two adjacent values can be in the solution.

For example, given an input array, our objective might be to find the maximum sum of chosen values in the array where we cannot choose adjacent values.

This problem is not the most straightforward because we cannot adopt a "greedy" solution by always choosing the largest numbers we see. Doing so may give us a suboptimal solution. For example, if the input array were [2, 4, 3], the optimal solution would be to pick 2 and 3, but if we had just chosen the largest of the first 2 numbers we looked at, we would have picked 4.

This is where recursion can help us, and dynamic programming can help optimise. Let's call this problem maxSumNoAdjacent. My code might look like the following.

// We would use the cache to store intermediate calculations
const cache = {};
const maxSumNoAdjacent = (arr) => {
  // Base case: If array empty, return 0
  if (arr.length === 0) {
    return 0;
  }
  // Base case: If array length 1, return the only value in array
  if (arr.length === 1) {
    return arr[0];
  }
  // If calculation done before, return calculated value
  if (cache[arr]) {
    return cache[arr];
  }
  // Calculate max value if we choose the first element
  const resultIfChooseFirst = arr[0] + maxSumNoAdjacent(arr.slice(2));
  // Calculate max value if we do not choose the first element
  const resultIfChooseSecond = maxSumNoAdjacent(arr.slice(1));
  // Return the resulting value that is larger if we "take or don't take"
  return Math.max(resultIfChooseFirst, resultIfChooseSecond);
}

Notice in the final line of the code we return the maximum of values when we "take or don't take".

Exercises

Part 1

Please fork starter code Repl and attempt solutions there. Feel free to compare with reference solutions after attempting each problem. Conway and Catalan problems are optional. Have fun!

Part 2

Part 3

Part 4

More Comfortable

Further Reading

()

Climbing Stairs ()

Min Cost Climbing Stairs ()

House Robber ()

Maximum Points You Can Obtain From Cards ()

Minimum Operations to Reduce X to Zero ()

Coin Change (, )

, a DP problem that involves storing intermediate calculations in a table with dimensions m by n, where m is the length of 1 input word and n is the length of the other.

🧮
Rocket DP intro problems
solutions
LeetCode
LeetCode
LeetCode
LeetCode
LeetCode
HackerRank
LeetCode
Video solution to Longest Common Subsequence
Introduction to dynamic programming