LeetCode 1143: Longest Common Subsequence asks: Given two strings, return the length of their longest common subsequence. As we saw when solving the Longest Increasing Subsequence problem, a subsequence is formed by selecting elements from the input, with the only restriction being that they remain in their original order. For the LCS problem, if our […]
ContinueMultidimensional Dynamic Programming
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 […]
ContinueLeetCode 300: Longest Increasing Subsequence
Last week, we looked at a problem involving a subarray. A subarray is a contiguous sequence of elements from an array, meaning we can’t skip any elements when building the answer. A subsequence, on the other hand, allows us to skip elements, though the elements in the subsequence still need to stay in their original […]
ContinueLeetCode 53: Maximum Subarray
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: […]
ContinueDynamic Programming States and State Transitions
Using what we have covered so far, you can analyze a dynamic programming problem and solve it using DP techniques and concepts. But after solving a few problems, you might still feel like you have to invent a new solution each time. In the introduction to this year’s project, I promised to explain a process […]
ContinueDynamic Programming vs. Greedy Algorithms
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.
ContinueLeetCode 55: Jump Game
Let’s solve LeetCode problem 55 (Jump Game) using dynamic programming. Next week, we’ll consider a sneaky aspect of this problem. The problem: You are playing a game on a number line where the aim is to reach position n-1 starting from position 0. As input, you get an array nums of size n containing non-negative […]
ContinueTop-Down and Bottom-Up Dynamic Programming
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.
ContinueDynamic Programming Elements for LeetCode 322: Coin Change
To see how the elements of dynamic programming come together in a real problem, let’s explore the classic dynamic programming problem Coin Change (LeetCode 322).
ContinueWhat Is Dynamic Programming?
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 […]
Continue- « Previous Page
- 1
- 2
- 3
- 4
- …
- 50
- Next Page »