Dynamic Algorithm Summaries
Oct 21, 2024
Here are the summaries for the Dynamic algorithms in Leetcode's Blind 75. Check out the previous post on Trees. Dynamic programming is a method used to solve complex problems by breaking them down into simpler subproblems. Unlike the other categories I have for the Blind 75, this is not a data structure, but more about the types of solutions that work well with them.
Climbing Stairs
Given an integer representing the number of stairs, calculate how many ways the stairs can be climbed by taking 1 or 2 steps at a time.
Solution with O(n) time / O(1) space
The trick is that for any stair, you can recursively calculate the number of ways to reach it as (the result from 2 steps down) + ( the result from 1 step down). Iterate through the number of stairs, initializing the 0th step and 1st step as 1.
Coin Change
Given an array of coin denominations and an amount to make change for, return the minimum coins possible to add up to the amount, if possible.
Solution with O(a*n) time / O(a) space, where a is the amount, and n is the number of denominations
Recursively try subtracting each coin from the amount until it reaches 0 or not. To improve speed, cache the sub-solutions to minimum coins per amount.
Longest Increasing Subsequence
Given an array of integers, return the length of the longest increasing subsequence (not necessarily consecutive).
Solution with O(n*Log(n)) time / O(n) space
Create an array that is the same length as the input, initialize with the first element of the input, and the max integer for the rest of the elements.
Iterate through the numbers in the input, for each number, save it to the array (using binary search as an optimization) at the lowest index that would keep the array sorted (possibly overwriting another number).
The length of elements inserted is the answer. The numbers in the result array won’t necessarily be the actual longest subsequence, but this still works because shorter subsequences will only overwrite the beginning of a longer subsequence.
Longest Common Subsequence
Given two strings, find the longest common subsequence of characters, not necessarily consecutive.
Solution with O(mn) time / O(mn) space
Considering the subsequence can match at any point in the strings, the trick is to save the max subsequence found so far in a 2 dimensional format. Iterate through the characters in the strings, for each combination:
- Save the “max subsequence so far” into the corresponding position in the 2d array
- If the characters don't match, copy the higher of the previous row or column in the array
- If they do match, copy the previous value subtracting one row and one column, then add 1
Word Break Problem
Given a string, and a list of words, determine if the string is made up of any combination of the list of words.
Solution with O(n^3) time / O(n+k) space where n is the length of the string, and k is the characters in all the words
The difficulty of this problem is that words can overlap and mesh together, so a brute force solution would be incredibly time and space inefficient. The trick is to work your way from one side of the string, saving the index of the end of every substring that is in the dictionary.
When looping through the string, you don’t need to know the exact words that were in the string, you just need to know if a substring is a valid word and it starts at the end of a valid word. You can use a boolean array the length of the string to keep track of the valid substrings.
Combination Sum
Given an array of distinct positive integers, and a target value, return the number of combinations that add up to the target.
Solution with O(n*t) time / O(t) space, where n is the elements in the array and t is the value of the target
An easier way to think about this is to break down the problem into a subproblem: What if you subtracted one input value from the target? Then you would have a different target value, and the same array of integers to try. Whenever the target becomes zero, that’s one more combination for the result.
To make a solution with memory to prevent recalculating combinations, you can basically save each sub-target combination.
Make an array the size as the target value to save the number of combinations that add up specifically to each sub-target. This means you can just iterate through the sub-target array (initialized as 1 for the 0th sub-target), at each point, attempting to subtract the input integers from the current value, and carrying over the sub-target value if there is any.
House Robber
Given an array of numbers representing the amount of money at each house on a street, return the maximum amount of money you can rob without going to adjacent houses.
Solution with O(n) time / O(1) space
Iterate through the array, keeping track of two variables:
- The first will track the maximum amount of money gained from robbing the previous house (plus the maximum valid sequence of houses before that)
- The second will track the maximum amount of money gained from robbing the current house (plus the maximum valid sequence of houses before that)
The larger number at the end is the answer.
House Robber II
The problem is almost the same as the previous one, except the first and last houses connect in a circle (which makes them adjacent).
Solution with O(n) time / O(1) space
You can solve this the same as the previous problem, except you’ll need two loops or extra variables to calculate the maximum money gained from robbing:
- first house → second to last house vs
- the second house → the last house
Decode Ways
Given a string of numbers, where the numbers 1-26 represent the letters a-z, return the number of ways to decode the string into letters.
Solution with O(n) time / O(n) space
This can be solved with tabulation by recognizing that the encoded letter could only be 1 or 2 characters long, so we can build the number of ways to decode each substring, and use the previous results to add onto the next substring. Very similar to “Climbing Stairs” except now you need to check if the string can be decoded.
Unique Paths
Given an m x n grid, return the number of unique paths from the top left corner to the bottom right. You can only move right and down.
Solution with O(n*m) time / O(n*m) space
This could be solved using pure math, but a more general approach uses dynamic programming.
Iterate through all rows and columns, tabulating the number of unique paths to get to each point.
Jump Game
Given an array of integers, representing the maximum number of spaces you can move towards the end of the array, determine if you can move from the start of the array to the end.
Solution with O(n) time / O(1) space
Iterate through the array, checking the maximum reachable index by adding the current index to the current value. Continue replacing the value with the maximum reachable index, until you reach the end of the array, or you can no longer move forward.