Interview Cheat Sheets | Dynamic Programming Cheat Sheet

December 31st, 2023

Introduction

This article will serve to further summarize the excellent overview of dynamic programming from the tech interview handbook.

Overview

Dynamic Programming (DP) is usually used to solve optimization problems. The only way to get better at DP is to practice. It takes practice to be able to recognize that a problem can be solved by dynamic programming.

Techniques

• Sometimes storing the last two values or the last two rows of the matrix in memory, as compared to the entire dynamic programming table, will suffice.

Essential Questions

• Climbing Stairs - My solution
• Coin Change - My solution
• House Robber - My solution
• Longest Increasing Subsequence

Recommended Practice Questions

• 0/1 Knapsack or Partition Equal Subset Sum
• Longest Common Subsequence
• Word Break Problem - My solution
• Combination Sum - My solution
• House Robber II
• Decode Ways
• Unique Paths - My solution
• Jump Game