Dynamic Programming Flashcards
- Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
創一個nxn的DP matrix，DP[i][j]代表i~j是否是回文，
P(i,j)=(P(i+1,j−1) and Si ==Sj)
DP[i][j] 是否回文 根據DP[i+1][j-1] 且Si ==Sj，所以可以如此DP下去。
先把dp[i][i] 都設定好
dp[i][i+1]也設定好
最後就是for loop去填其他dp
for loop 有一點trick
for j in xrange(len(s)):
for i in xrange(j - 1):
loop 的走法可以是一個col一個col往右走(這個比較好寫)
也可以是走斜的格子(換句話說就是substring固定長度)
目的就是要先把Dp[i+1][j-1]做完
- Regular Expression Matching
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.
’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". Example 2:
Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3:
Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)". Example 4:
Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab". Example 5:
Input:
s = “mississippi”
p = “misisp*.”
Output: false
It can use backtracking or DP.
Backtracking:
compare first letter every recursive.
分為兩種可能來return
if len(p) >= 2 and p[1] == ‘*’:
else
DP:
# dp initial
dp = [[False for _ in xrange(len(p) + 1)] for _ in xrange(len(s) + 1)]
dp[0][0] = True
for j in xrange(1, len(dp[0])):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2] # Define Transfer function for i in xrange(1, len(s) + 1):
for j in xrange(1, len(p) + 1):
if s[i - 1] == p[j - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
if s[i-1] == p[j-2] or p[j-2] == '.': # star means repeat preceding element
dp[i][j] = dp[i][j-2] or dp[i-1][j] # 就算星號前字母和s的相同，a*也可能代表重複0次，所以還是要考慮dp[i][j-2]
else: # star means zero
dp[i][j] = dp[i][j-2]
else:
dp[i][j] = False
0 a a b 0 o x x x c x x x x * o x x x a x o x x * o o o x b x x x o
if p[i-1] == s[j-1] or p[I-1] == '.' :
dp[i][j] = dp[i-1][j-1]
else:
if p[I-1] == '*':
if p[I-2] == s[j-1] or p[I-2] == '.':
dp[i][j] = dp[i-1][j] or dp[i-2][j]
else:
dp[i][j] = dp[i-2][j]
else:
dp[i][j] = False
- Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”
~~~
Example 2:
~~~
Input: “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”
~~~
~~~
- DP
Use DP. Initial a DP array, represent the longest valid parentheres end at i.
the transistion function.
Transition function:
dp[i] = dp[i-2] + 2 if “…..()”
2 + dp[i-1] + dp[i - dp[i-1] - 2] if “…..))” if i - dp[i-1] - 1 - 1 >= 0 and s[i - dp[i-1] - 1 - 1] == ‘(‘:
Only tow kind of situation the dp has value.
end with ‘()’, ‘))’. If end wirt ‘(‘, always invalid.
And the transistion function can be done depend on this two condition.
2. Stack
Using a stack to parse the parentheses is a very nature way to figure out when ‘)’ is coming, is there are enough ‘(‘. And you push the index into stack. So that you can calculate the length.
3. without extra space
parse from left. Only when left and right are equal. This is a valid subsequence.
And then parse from right. return the max
((()()(((
- Edit Distance
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2:
Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)
- DP
* 思路
Define dp[i][j] as the edit distance between word1[:i] and word2[:j].
Transition function:
if last letter is the same
d[i][j] = d[i-1][j-1]
else
dp[i][j] = 1 + (dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) (insert, delete, replace: means the edit distance of after doing these move)
h o r s e
0 1 2 3 4 5
r 1 1 2 2 3 4
o 2
s 3
D(“abbc”, “acc”)
=D(“abb”, “ac”). # no edit on last c
= 1 + min(D(“ab”, “ac” ), #delete ab[b] 如果我知道D(“ab”, “ac” )那我就先delete在edit
D(“abb”, “a”), #insert a[c]如果我知道D(“abb”, “a”) 就先edit在insert
D(“ab”, “a”)). # replace. ab[b] to a[c] 如果我知道D(“ab”, “a”)就replace b to c在edit
- Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
Above is a 7 x 3 grid. How many possible unique paths are there?
Example 1:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right Example 2:
Input: m = 7, n = 3
Output: 28
Constraints:
1 <= m, n <= 100
It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.
Use 2d dp array or 1d is fine.
dp = [0 for _ in xrange(m+1)]
dp size need to be m+1, n+1. Because for the first element need a dp[I-1] to get the do[I]. So we need initial the dp 1 longer and initialize the first row, col.
- Unique Paths II
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
Note: m and n will be at most 100.
Example 1:
Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right
Use 2d dp array or 1d is fine.
dp = [0 for _ in xrange(m+1)]
dp size need to be m+1, n+1. Because for the first element need a dp[I-1] to get the do[I]. So we need initial the dp 1 longer and initialize the first row, col.
if there is a obstacle just let the dp[I][j] = 0
- Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
dp[n+1][m+1]
dp = [float(‘inf’) for _ in xrange(len(grid[0]) + 1)]
initialize as float(‘inf’) because the min
Transition function
dp[j] = min(dp[j], dp[j-1]) + grid[i-1][j-1]
- Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).
Example 2:
Input: “226”
Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).
Use 1D DP array.
transition function
if not s or s[0] == '0': return 0
dp = [0 for _ in xrange(len(s) + 1)]
dp[0] = 1
dp[1] = 1
for i in xrange(2, len(dp)):
if s[i-1] != '0':
dp[i] += dp[i-1]
if s[i-2] == '1' or s[i-2] == '2' and 0 <= int(s[i-1]) <= 6: dp[i] += dp[i-2]
return dp[-1]- Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?
Example:
Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST’s:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Constraints:
1 <= n <= 19
1D DP array
choose a number as root.
Then you can divide all number into two groups.
Get each group possible unique tree from dp.
Then multiply the number of left and right subtree. This the answer
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0 for _ in xrange(n+1)]
# Transition Function
# 1: 1
# 2: 2
# 3:
dp[0] = 1
dp[1] = 1
for i in xrange(2, len(dp)):
for j in xrange(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[-1]
- Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
Example:
Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Constraints:
0 <= n <= 8
- if the output need to list all kind of possible combination. It must use recursive. You can also add a memo dictionary to implement DP recursive.
- First idea come out my mind is use a backtracking to iterative 1~n, Add a node in each recursive function. And delete the node after return the function. But this method can’t works for this problem. Because if you delete the node after return the function. The node in the result also are deleted. That will make the results are all None.
Backtracking build up the combination when enter next recursive.
But this problem, we need to let the recursive build sub combination and gather all sub combination when exist the recursive. And this idea is Divide and Conquer. - How to implement Divide and Conquer.
1,2,3,4,5
for loop choose a node as the root of the sub-tree for example 3. Then 1,2 are the left tree of 3. 4,5 are the right tree of 3. let node = TreeNode(3)
And call left = dfs(1,2), right = dfs(4,5). left and right a list of many combination. for loop all left and right combination and build all combination of tree rooted as 3.
- Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
Use 2d array is easier.
Use dp = [[0 for _ in xrange(len(triangle[-1])+1)] for _ in xrange(len(triangle)+1)] is more complicate
you can use
dp = [[0 for _ in xrange(len(triangle[-1]))] for _ in xrange(len(triangle))]
Transition function: dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])
if it is the first element in the row, left = float(‘inf’). if it is the last element in the row, right = float(‘inf’)
- Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
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
It is a kind of jump game. the jump step is depend on the word in dictionary words.
Initial a 1d dp array.
two for loop.
first, loop all letter in s.
Then from the I letter loop back to front. And check is there a substring in wordDict.
build a set
wordset = set()
for w in wordDict:
wordset.add(w)
dp = [0] * (len(s) + 1)
dp[0] = 1
# dp[i] = dp[i-1] s[i:i+1] in wordset + dp[i-2] + ...
for i in xrange(1, len(s) + 1):
for j in xrange(i):
if s[j:i] in wordset:
dp[i] += dp[j]
return dp[-1] > 0
- Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ] Example 2:
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word. Example 3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
Use recursive to solve this problem. Also use memo to memorize the sub problem ans.
Every recursive
loop the string and divide the string into left and right.
check if left in wordDict. If True dfs(right) and append answer.
Time Complexisty O(2^n)
- Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
This problem need two dp
one for max product dp_max. one for min product dp_min
思路其實是dp_max去紀錄nums[any previous~i]的最大值，dp_min去紀錄nums[any previous ~i]的最小值
dp[i]會一直把i以前最大的值留下來，所以下一次只需要讓nums[i-1]和dp[i-1]去乘就可以，不用在考慮前面。
Transition function is:
dp_max[i] = max(nums[i-1], dp_max[i-1] * nums[i-1], dp_min[i-1 * nums[i-1]])
- Maximal Square
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
Transition function is dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1.
There is one trick to speed up. if the res is >n. If the rest of the row is smaller than n. There is no need to check them.
