Leetcode: Dynamic Programming

Question 1

Strategies for dynamic programming

Answer 1

1. use dp array, dp=[1]nums OR dp = [0]+[1]nums, remember we do need a base case for this scenario. don’t be afraid to add the 0 +len list! it usually works
2. when comparing 2 values against each other, you might need to use a graph with x/y being the length of each respective value
3. think Pow(x,n) problem

Question 2

Longest increasing subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Answer 2

brute force is you make a dp=[], perform a double loop, and use the nums array to determine if the value you are at is greater than the value at the nums, then we use the dp array to determine what the new value at that num index should be

time: O(n^2), space: O(N)
- —’’’
- —Once you realize the first iteration does nothing, you can optimize to range(1, len(nums)), but don’t worry about that at first,
- —bc you are more likely to fuck up, the first implementation does not have to be 100% right, just needs to work
- —’’’
- —def answer1(self, nums):
- ——-dp = [1]*len(nums)
- ——-m=1
- ——-for i in range(len(nums)):
- ———–for j in range(len(nums[:i])):
- —————if nums[i]>nums[j]:
- ——————-dp[i]=max(dp[i], dp[j]+1)
- ——————-m=max(m, dp[i])
- ——-return m
1. after you see the brute solution, you can see we are doing some type of search on a list, this search can be improved with binary search if instead of a dp array we used a custom array
2. make an array with the first number in it to start
3. if the num in the list is greater than the last index of our array (the largest value at any time), we append it
4. if not, we search the array for the first index that is larger than it and replace it
5. At this point you might think what if we have [1,3,4,2] and we replace 3 with 2 with this method, it ultimately does not affect the end result be we really only care about the end index and the total length at the end. if we have [1,3] and we find 2, we want to replace 3 with 2; this is because later if we see 3, we want to append that to increase the total length. But if we have 1,3,4 and see 2, replacing 3 with 2 has no effect. It does alter the “ordering” but that isn’t what we care about

time: O(log(n)*n), we search through the entire num list and do a binary search each time
space: O (n), we can have a list of all the numbers at worst

• —def optimal2(self, nums):
• ——-sub = [nums[0]]
• ——-for num in nums[1:]:
• ———–if num>sub[-1]:
• —————sub.append(num)
• ———–else:
• —————i = self.binary_search_iterative(sub, num)
• —————sub[i]=num
• ——-return len(sub)

Question 3

Longest common subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.

Answer 3

brute, get a set of all possible combinations of both strings, check 1 subset is in the other, then compare them to the max length, return max length
time: 2^len(strings), space = 2^len(string). the total number of a subsequence of a string is 2^len(string)

• —def brute(self, t1, t2):
• ——-s1 = self.all_subsequences(t1)
• ——-s2 = self.all_subsequences(t2)
• ——-m=0
• ——-for x in s1:
• ———–if x in s2:
• —————m=max(m, len(x))
• ——-return m

!!! if you use lru_cache it needs to be a nested function or else lru_cache caches self too

1. dynamic programming, in this situation we are comparing 2 strings against each other, so we can use a matrix
2. create a matrix with default values of 0, make sure the columns correlate to the inner loop and the rows correlate to the outer loop (for my own visualization)
3. WHAT IS THE BASE CASE?
4. draw it out
5. there are 2 situations, if the character is equal or if it is not
6. if it is not, we take the max value of what is above/side
7. if it is equal, we take the previous diagonal value and add 1 to it
8. the last value in the grid will be the maximum, so return that as the solution

time: O(NM), the length of both strings
space: O(nm), the grid

• —def full_grid(self, text1, text2):
• ——-row = len(text1) - 1
• ——-col = len(text2) - 1
• ——-grid = [[0 for i in range(len(text2) + 1)] for i in range(len(text1) + 1)]
• ——-for row in range(len(text1) -1, -1, -1):
• ———–for col in range(len(text2) - 1, -1, -1):
• —————if text2[col] == text1[row]:
• ——————-grid[row][col] = grid[row + 1][col + 1] + 1
• —————else:
• ——————-grid[row][col] = max(grid[row][col + 1], grid[row + 1][col])
• ——-return grid[0][0]

1. if you realize that you only care about the current/previous rows, not the entire grid, then you can do the following solution!
2. Make sure to set the previous=current after the inner loop and set current=previous (or 0’s). If we just set prev=current, then they both point at the same object in memory and modifications on 1 affect the other, which is bad
3. once the loop ends, the previous list becomes the most current, so make sure to return the previous[0]
4. must make sure the length of the lists is the length of the item in the inner loop, since col is the value we use to index the lists, they need to be equal
5. pad the lists with 1 extra 0 and go in reversed order. This prevents you from having to check if the index is in range of the list

time: O(N*M), the length of both strings
space: O(min(M, N)), 2 lists that have the min length between them

• —def optimized_space(self, text1: str, text2: str) -> int:
• ——-if len(text1) < len(text2):
• ———–text1, text2 = text2, text1
• ——-cur, prev = [0] * (len(text2) + 1), [0] * (len(text2) + 1)
• ——-for row in range(1, len(text1) + 1):
• ———–for col in range(1, len(text2) + 1):
• —————# this helps us with the out of index error while properly indexing the strings
• —————if text1[row - 1] == text2[col - 1]:
• ——————-cur[col] = prev[col - 1] + 1
• —————else:
• ——————-cur[col] = max(cur[col - 1], prev[col])
• ———–prev, cur = cur, prev
• ——-return prev[-1]

Question 4

Integer break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Answer 4

Dynamic programming

1. 3’s give the largest product. 33 > 22*2
2. Create a map that contains each input and their max product output (dynamic programming)
3. Check if input is in map, if so return value calculated
4. Iterate over range(2, n). The base input is 1*(n-1) so we dont need to start at 1
5. base max is input-1
6. Update map as frequently as possible to help other recursive calls

Time: O N^2 without dynamic programing, but with dp we can get closer to linear time
Space: O N, linear space bc we store each value for n-2 until it is 0

class IntegerBreak:

• —def answer(self, i):
• ——-#if 0, return 0
• ——-if i<=2:
• ———–return 1
• ——-return self.answer_helper(i, {})
• —def answer_helper(self, i, hm):
• ——-if i==0 or i==1:
• ———–return 1
• ——-elif i==2:
• ———–return 2
• ——-elif i==3:
• ———–return 3
• ——-elif i in hm:
• ———–return hm[i]
• ——-best=i-1
• ——-for t in range(2, i):
• ———–best=max(best, t*self.answer_helper(i-t, hm))
• ——-hm[i]=best
• ——-return best

Question 5

Number of ways to climb a staircase

Hi, here’s your problem today. This problem was recently asked by LinkedIn:

You are given a positive integer N which represents the number of steps in a staircase. You can either climb 1 or 2 steps at a time. Write a function that returns the number of unique ways to climb the stairs.

# def staircase(n):
#   # Fill this in.

# print staircase(4)
# # 5
# print staircase(5)
# # 8

Answer 5

Brute force is recognize it is a fib sequence and return stanard fib,

• —def fib(self, index):
• ——-if index<=1:
• ———–return 1
• ——-return self.fib(index-1) + self.fib(index-2)

time: O(n), we must loop through the range once
space: constant, we do not store any additional data

1. dynamic programming
2. understand that 2^n solutions can usually be optimized
3. you can do the manual calculations yourself by iterating over a range of values from 0 to step value
4. make sure to know if 0 index refers to the first fib number of if they are beginning their sequence at 1, that will change how you write the solution. If 1 refers to the 0 index under normal terms, just do range(n-1)
5. start off by writing out the answers to 3, 4, 5, you should realize it is the fib sequence

• —def best(self, n):
• ——-first=0
• ——-second=1
• ——-for _ in range(n):
• ———–first, second = second, first+second
• ——-return second

Question 6

coin change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

if amount is 0, you can return 0 or 1 (some people want you to return 1, just add an initial if statement)

Answer 6

1. dynamic programming
2. must create a list of [0]+[inf]*amount, this gives us a list to iterate through
3. we use the indexes as “amounts” and reference them if another (index - coin) equals it, because we will know how many coins it took to make that index (amount)
4. we need to add [0] to the front because if when (index-coin)=0, we do not want to reference index 1 since that would be inaccurate.
5. the last item in the list we created will the min coins needed to sum to the amount (index), so return list[-1], if the list[-1] is equal to the max intial value we added, return -1

time: O(amount* coins), for each index we go through each coin
space: O(n), linear space since we instantiate an array

• —def answer(self, coins, amount):
• ——-amount_list = [0] + [float(‘inf’)]*amount
• ——-for i in range(1, amount+1):
• ———–for coin in coins:
• —————if i - coin >= 0:
• ——————-amount_list[i] = min(amount_list[i], amount_list[i-coin] + 1)
• ——-return amount_list[-1] if amount_list[-1] != float(‘inf’) else -1

time: target^coins. worst case each value of the target sees each coin. you might think it is factorial, but that is not true. Think 100 with 1,2,3 coins, worst case there are about 100 solutions per coin, and each coin will have to see each other coin’s solutions each time they loop
space = target, the depth of the recursion tree at any given time
—-def brute(self, coins, target):
——–answer = self.brute_helper(coins, target)
——–if answer==float(‘inf’):
————return -1
——–else:
————return answer
——–
—-def brute_helper(self, coins, target):
——–if target==0:
————return 0
——–count=float(‘inf’)
——–for coin in coins:
————if coin<=target:
—————-count=min(count, 1+self.brute_helper(coins, target-coin))
——–return count

Question 7

word break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:

Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: false

Answer 7

Time complexity : O(2^n). Given a string of length n, there are about n ways to split it into two parts.
At each step, we have a choice: to split or not to split. In the worse case,
when all choices are to be checked, that results in O(2^n). This is because we split each word into 2, then each word from that into 2
, and so on,
recognize that each entry can propagate into many more entries, and if they all do not return anything we have to go back to the start,
increment 1, and do it again, these are usually exponential in some fashion

Space complexity : O(n). The depth of the recursion tree can go upto n.

• —def brute(self, s, wordDict):
• ——-wd = set(wordDict)
• ——-self.memo={}
• ——-return self.brute_helper(s, wd, 0)
• —def brute_helper(self, s, wordDict, start):
• ——-if len(s)==start:
• ———–return True
• ——-for i in range(start+1, len(s)+1):
• ———–if s[start:i] in wordDict and self.brute_helper(s, wordDict, i):
• ——————-return True
• ——-return False

1. dynamic programming! the brute force solution offers us a great start, bc we can memoize
2. where do we memoize? If we started at index 3, and we could not produce a solution, that means index 3 doesn’t produce a solution.
3. dp array = len(string), initialize to None. Once a string doesn’t return anything, make the start index of the dp array = False
4. each iteration, if the dp array index is not None, return the memo[index] value

time: o n^3, n searches the initial string, and the recurion tree can become n^2, we reduce this from exponential because each combination of the strings will only be hit once bc of the memo in theory, n because we search the initial string, and n^2 because we have to search that string for each of its combinations at each character, so n*n^2 = n^3.

IN PRACTICE this is better than an O n^2 solution bc of the dynamic programming aspect (according to time on LC)

space: O(n), bc the recursion depth is only going to be the length of the initial string

• —def answer1(self, s, wordDict):
• ——-wd = set(wordDict)
• ——-self.memo=[None]*len(s)
• ——-return self.answer1_helper(s, wd, 0)
• —def answer1_helper(self, s, wordDict, start):
• ——-if start == len(s):
• —————return True
• ——-if self.memo[start] is not None:
• ———–return self.memo[start]
• ——-for end in range(start + 1, len(s) + 1):
• ———–if s[start:end] in wordDict and self.answer1_helper(s, wordDict, end):
• —————self.memo[start]=True
• —————return True
• ——-self.memo[start]=False
• ——-return False

Question 8

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Answer 8

brute is just multiplying x by itself n times

1. realize that 2^8 = 2^4 * 2^4. you can take this all the way home by a recursive function that performs some action and then calls itself with n//2
2. if n is negative, we need to invert x and make n positive
3. on an odd exponent, we need to subtract 1 from the exponent, perform the actions we do on evens, and multiply by x once
   BONUS
4. you think you can do the same basic thing, if n is negative, r=x, if even, r=r, the issue is that since we are doing a bottom-up solution, the x we multiplied on the odd exponent will be propagated through the answer, making it much larger than we expected
5. we need a way to have the even exponents do their thing, then when they hit an odd one, we multiply in our answer. much like how we did AAx, x is multiplied at the end, not the beginning
6. we need to make r=1, and c=x, each iteration c=c, but only when we get an odd number we do r=c first
7. hard to visualize, but if you take the recurisve solution down to n=0, then youll see it goes x11, then that x is carried into xAA, same thing we are doing here but at the beginning

time: O(log(n)), since determines how many times we do this, and n//2 each iteration, we get log(n)
space: log(n) as well, the depth of the recursion tree

class Solution:

• —def myPow(self, x: float, n: int) -> float:
• ——-if n == 0:
• ———–return 1
• ——-if n < 0:
• ———–x = 1 / x
• ———–n = -n
• ——-if n%2==1:
• ———–A = self.myPow(x, n // 2)
• ———–return A * A * x
• ——-else:
• ———–A = self.myPow(x, n // 2)
• ———–return A * A

time: O(log(n)), since determines how many times we do this, and n//2 each iteration, we get log(n)
space: constant, we do not create new objects

—-def optimal_iterative(self, x, n):
——–if n < 0:
————x = 1 / x
————n = -n
——–r=1
——–c=x
——–while n:
————if n%2==1:
—————-n-=1
—————-r *= c
# can have another if statement for even, not needed
————c *= c
————n//=2
——–return r

Question 9

square root x

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Answer 9

1. not intuitive tbh, but thing binary seach
2. instead of arr[mid] searching, we search on mid * mid. if mid * mid == x, then we found our value
3. it doesn’t work well for odd numbers, like 13. 13 gets us 6, mid is 4 and 16, then 3 and 9, then 4 and 16, which returns mid - 1 which is 3, root 13 is 3.6 so it is accurate

time: log(n), binary search is log n time
space: constant

class Solution:

• —def mySqrt(self, x: int) -> int:
• ——-if x < 2:
• ———–return x
• ——-left, right = 2, x // 2
• ——-while right >= left:
• ———–mid = (left + right) // 2
• ———–mid_val = mid * mid
• ———–if mid_val < x:
• —————left = mid + 1
• ———–elif mid_val > x:
• —————right = mid - 1
• ———–else:
• —————return mid
• ——-return right