Red-Green-Code

As we have seen in previous weeks, a key step in analyzing a dynamic programming problem is selecting state variables that identify the subproblems to be solved. The solutions to these subproblems are stored in a table, which allows us to retrieve them efficiently when they come up again. So far, we have looked at […]

The maximum subarray problem is famous enough to have its own Wikipedia page, and a named algorithm you can use to solve it (Kadane’s Algorithm). But rather than looking up the algorithm, we’ll derive the solution to LeetCode 53: Maximum Subarray using principles of dynamic programming. The problem statement is simple. Here’s the LeetCode version: […]

Last week, we looked at a dynamic programming problem for the Jump Game problem. If you implement that solution and run it on LeetCode, you’ll notice that your runtime and memory scores are very low compared to other users. Let’s see why that is.

To solve a problem using dynamic programming, you have to break it into subproblems, solve those subproblems, and use the results to solve the original problem. So the first step in solving a dynamic programming problem is defining what subproblems you need to solve.

Binary search is an algorithm. It provides step-by-step instructions for efficiently finding a value in a sorted list. A hash table is a data structure. It provides an efficient way to map keys to values. Dynamic programming is an algorithmic technique, or more formally, an algorithmic paradigm. Like divide and conquer, backtracking, or greedy, it […]