Dynamic Programming and Backtracking

Question 1

Write a function fib that takes in a number argument, n, and returns the n-th number of the Fibonacci sequence.

The 0-th number of the sequence is 0.

The 1-st number of the sequence is 1.

To generate further numbers of the sequence, calculate the sum of previous two numbers.

Solve this recursively. Also try with memoization.

Answer 1

def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
return fib(n - 1) + fib(n - 2)

O(2^n) / O(n)

^ Know how to explain and visualize the complexity using trees and call stack.

Question 2

How to break down and visualize recursive problems?

Answer 2

Use a tree-like structure with nodes.
Fib(6) depends on fib(5) and fib(4)

  6 5          4

Question 3

How does the call stack work? (if you visualize as tree)

Answer 3

It’s DFS (L, R, root) postorder?

Question 4

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer 4

• Base case, if n = 0 or n < 0
• Recursively call function on n - 1 and n - 2
• Add the two calls together
• Use memoization

Question 5

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.

Answer 5

• for coin in coins subtract coin from amount.
• to find the min out of all of the branches:

minVal = math.inf
for coin in coins:
minVal = min(minVal, 1 + self._coinChange(coins, amount - coin, hash))
hash[amount] = minVal

return minVal

O(n * m) / O(n)

Question 6

Can you hash a tuple?

Answer 6

YES!

Question 7

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Answer 7

• Helper function to track the max and min values of the grid as well as hash of (m, n) tuple to number of paths from that path.
• Base case if you reach the bottom left corner, or if you’re out of bounds, or if coordinates in hash.
• Add together the two recursive calls.

O(n * m) / O(m * n)

(you can also try the clever Neetcode solution)
https://www.youtube.com/watch?v=IlEsdxuD4lY&t=641s

Question 8

How do you calculate time complexity of dynamic programming problem?

Answer 8

• If it’s not memoized, it’s an exponential problem.
• The base is the max branches at each node (for binary tree, it’s 2)
• Exponent is the max height of the tree.
• Once you memoize, TC Is linear because you’re only visiting each possibility once before it’s hashed.

Question 9

FUNDAMENTAL DP PROBLEM - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Answer 9

(Also consider the iterative Neetcode solution later)

• Construct a decision tree: If you start from index 0, you can go to index (start + 2)
• Other cases are covered if you start from index 1
• So run the recursive function twice on “include all” and “exclude first” version of the array.

class Solution:
def rob(self, nums: List[int]) -> int:
return self._rob(nums, {}, 0)

def _rob(self, nums, hash, start):
    if start >= len(nums):
        return 0

    if start in hash:
        return hash[start]

    include = nums[start] + self._rob(nums, hash, start + 2)
    exclude = self._rob(nums, hash, start + 1)
    result = max(include, exclude)
    
    hash[start] = result
    return result

Bottom up DP solution:

• At each point in the array, you choose if you rob 2 houses before where you are, or 1 house before where you are based on which is greater.
• Then you update the pointers when you go on to the next position.

class Solution:
def rob(self, nums: List[int]) -> int:
rob1, rob2 = 0, 0
for n in nums:
temp = max(rob1 + n, rob2)
rob1 = rob2
rob2 = temp

    return rob2

Question 10

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Answer 10

• The key is to find max(rob(nums[1:], rob(nums[:-1])
• The rest is the same as House Robber I.

Question 11

Given a string s, return the longest
palindromic

substring
in s.

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:

Input: s = “cbbd”
Output: “bb”

Answer 11

• Dynamic programming makes this problem more complicated.
• Loop through each character and consider it the consider of the palindrome.
• Use an “expand” function to L– and R++, but run it twice so you cover even and odd palindromes.

class Solution:
def longestPalindrome(self, s: str) -> str:
res = ‘’
for i in range(len(s)):
l, r = i, i
res = max(res, self.expand(i, i, s), self.expand(i, i + 1, s), key=len)
return res

def expand(self, l, r, s):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l + 1:r]

O(n^2) / O(n)

Question 12

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:

Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Answer 12

• Loop through all chars, considering each as midpoint.
• Start expanding from the mid point and count++ every time it’s a still a palindrome.
• NOT DYNAMIC PROGRAMMING SOLUTION

class Solution:
def countSubstrings(self, s: str) -> int:
count = 0
for i in range(len(s)):
count += self._countSubstrings(i, i, s)
count += self._countSubstrings(i, i + 1, s)
return count
def _countSubstrings(self, l, r, s):
count = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1
r += 1
return count

Question 13

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

“AAJF” with the grouping (1 1 10 6)
“KJF” with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Answer 13

• When you take one-digit num or two-digit num, you can ignore that part. Just consider what comes after it.
• String splicing is slow, you can use only the index, starting at index 0 and recursively calling on i + 1 and i + 2.
• If i == len(s) return 1 because you’ve gone through the whole str and the whole this is valid.
• If str starts with 0, return 0.

class Solution:
def numDecodings(self, s: str) -> int:
return self._numDecodings(s, 0, {})

def _numDecodings(self, s, i, memo):
    if i in memo:
        return memo[i]
    if i == len(s):
        return 1
    if s[i] == '0':
        return 0
    
    result = self._numDecodings(s, i + 1, memo)

    if i + 1 < len(s) and (10 <= int(s[i:i + 2]) <= 26):
        result += self._numDecodings(s, i + 2, memo)
    memo[i] = result
    return result

Question 14

Given an integer array nums, find a
subarray
that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Answer 14

Not recursive DP.
- You want to track the maximum and minimum at any given point starting from the beginning.
- minimum, maximum, result
- loop through and calculate min and max of (min * num, max * num, num)
- This works because whenever you get a minimum number, it’s going to flip a the minimum to the maximum and vice versa.

Question 15

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

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Answer 15

• Bottom up dynamic programming.
• The LIS from the last index is 1.
• So build it up from end to beginning.
• Loop through backwards, then check all indices after it to see if the number is greater, and the LIS from that point.

O(n^2)

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
maxList = [1 for i in range(len(nums))]

    for i in range(len(nums) - 1, -1, -1):
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]:
                maxList[i] = max(maxList[i], maxList[j] + 1)

    return max(maxList)

Question 16

What’s the 3-step approach you can use to think about DP problems?

Answer 16

1. Decision tree
2. Recursion/DFS with caching
3. DP (bottom up)

Question 17

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”.

Answer 17

• Bottom up DP, where you iterate backwards through the string checking if you can form a word from each starting index.
• the DP array is initialized with False for each string index. Append True at the end to account for when you get the first match and i == len(str)
• Every time you match a word, you check if the index after it is “wordBreakable” and set current i to True.
• Return DP[0] when finished.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
breakList = [False for i in range(len(s) + 1)]
breakList[-1] = True

    for i in range(len(s) - 1, -1, -1):
        for w in wordDict:
            if s[i : i + len(w)] == w and breakList[i + len(w)]:
                breakList[i] = True

    return breakList[0]

Question 18

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the
frequency
of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Answer 18

• Backtracking
• Create a decision tree starting from 0 and add numbers until you reach the target.
• To eliminate duplicates, this has to be a binary decision tree, where on one side you include the first value of candidates, on the other side you exclude it. (do this with a pointer)
• When you hit the target value, you append to the global result list. Return nothing.
• O(2 ^ target) / O(t)

class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []

    def dfs(i, curList, total):
        if total == target:
            res.append(curList)
            return
        if total > target or i >= len(candidates):
            return
        
        dfs(i, curList + [candidates[i]], total + candidates[i])
        dfs(i + 1, curList, total)

    dfs(0, [], 0)
    return res

Question 19

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Answer 19

• Backtracking
• Loop through all cells on grid and call DFS
• Track a visited set and the current index of the target word you’re looking at.
• Check current cell against word[i]

O(n * m * 4^(len(word))) - it’s about the best you can do with this problem.

Question 19

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Answer 19

• Backtracking
• Loop through all cells on grid and call DFS
• Track a visited set and the current index of the target word you’re looking at.
• Check current cell against word[i]

O(n * m * 4^(len(word))) - it’s about the best you can do with this problem.

Question 20

Given an integer array nums, find the
subarray with the largest sum, and return its sum.

(subarray means it’s contiguous)

Answer 20

• Use Kadane’s Algorithm
• You’re going through the array and adding each number to the sum, keeping track of the max
• BUT - If the sum is ever negative, reset the sum to 0def maxSubArray(self, nums: List[int]) -> int:
  res = -math.inf
  cursum = 0
  for num in nums:
  if cursum < 0:
  cursum = 0
  cursum += num
  res = max(res, cursum)
  return res

Question 21

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Answer 21

• Like DP but greedy.
• Track the “goal” index - starting from the end of the array
• Iterate backwards through the array
• If goal is reachable from current index, update the goal.

O(n)

def canJump(self, nums: List[int]) -> bool:
    goal = len(nums) - 1
    for i in range(len(nums) - 2, -1, -1):
        if goal - i <= nums[i]:
            goal = i
    
    return goal == 0