Dynamic programming is one of the hot interview topics frequently asked during technical interviews. If you are applying for a software engineering role, this blog will provide you with an overview of dynamic programming and a list of practice problems for you to familiarize yourself with.
To illustrate this, imagine one day your friend comes to you with a large complicated puzzle, which in itself contains multiple smaller puzzles. You, excited to get started, pull up your sleeves and begin solving the smaller puzzles immediately. Not long into this task, you realize you have seen and solved these puzzles before. But you can't remember how you did it previously, or what the solution was. This time will be different! You decide to store the solution of each of the small puzzles you solve, in case you encounter them again. It turned out to be a great idea, as saving the results of the sub-puzzles saved you much time and unnecessary repeating of work. Because of this, you ended up solving the large complicated puzzle in a much shorter timeframe. This is the idea behind dynamic programming; avoid recalculating the same subproblems by storing intermediate results and then re-using the stored results when needed.
Below, I summarized a list of dynamic programming interview questions and answers from Leetcode to help you better understand the topic. Happy coding!😄
https://leetcode.com/problems/house-robber/
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * (n + 1)
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]
https://leetcode.com/problems/house-robber-ii/
class Solution:
def rob(self, nums: List[int]) -> int:
def helper(ls):
n = len(ls)
dp = [0] * (n + 1)
dp[1] = ls[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + ls[i - 1])
return dp[n]
if len(nums) == 1: return nums[0]
return max(helper(nums[1:]), helper(nums[:-1]))
https://leetcode.com/problems/house-robber-iii/
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def dfs(root):
if not root: return [0, 0]
l, r = dfs(root.left), dfs(root.right)
ans = [0, 0]
ans[0] = max(l[0], l[1]) + max(r[0], r[1])
ans[1] = root.val + l[0] + r[0]
return ans
return max(dfs(root))
https://leetcode.com/problems/delete-and-earn/
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
dp = [0] * 10001
for x in nums:
dp[x] += x
for i in range(2, len(dp)):
dp[i] = max(dp[i - 1], dp[i - 2] + dp[i])
return dp[10000]
https://leetcode.com/problems/pizza-with-3n-slices/
class Solution:
def maxSizeSlices(self, slices: List[int]) -> int:
def helper(ls):
n = len(ls)
k = (n + 1) // 3
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, k + 1):
dp[i][j] = max(dp[i - 1][j], (dp[i - 2][j - 1] if i - 2 >= 0 else 0) + ls[i - 1])
return dp[n][k]
return max(helper(slices[1:]), helper(slices[:-1]))
https://leetcode.com/problems/paint-house/
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
dp = [[0] * 3 for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(3):
dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + costs[i - 1][j]
return min(dp[n])
https://leetcode.com/problems/paint-house-ii/
class Solution:
def minCostII(self, costs: List[List[int]]) -> int:
n, k = len(costs), len(costs[0])
dp = [[inf] * k for _ in range(n + 1)]
dp[0] = [0] * k
for i in range(1, n + 1):
for j in range(k):
for h in range(k):
if j != h:
dp[i][j] = min(dp[i][j], dp[i - 1][h] + costs[i - 1][j])
return min(dp[n])
https://leetcode.com/problems/paint-fence/
class Solution:
def numWays(self, n: int, k: int) -> int:
same, diff = 0, k
for i in range(1, n):
same, diff = diff, (same + diff) * (k - 1)
return same + diff
https://leetcode.com/problems/paint-house-iii/
class Solution:
def minCost(self, houses: List[int], cost: List[List[int]], m: int, n: int, target: int) -> int:
dp = [[[inf]*(n+1) for _ in range(target+1)] for _ in range(m+1)]
dp[0][0] = [0]*(n+1)
for i in range(1, m+1):
for j in range(1, target+1):
if houses[i-1] == 0:
for k in range(1, n+1):
for prek in range(1, n+1):
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-(k!=prek)][prek]+cost[i-1][k-1])
else:
for prek in range(1, n+1):
dp[i][j][houses[i-1]] = min(dp[i][j][houses[i-1]], dp[i-1][j-(houses[i-1]!=prek)][prek])
ans = min(dp[m][target])
return ans if ans != inf else -1
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
buy = prices[0]
for p in prices:
buy = min(buy, p)
profit = max(profit, p - buy)
return profit
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
profit = 0
for i in range(1, n):
profit += max(0, prices[i] - prices[i - 1])
return profit
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
k = 2
dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
for i in range(k + 1):
dp[1][i][1] = -prices[0]
for i in range(2, n + 1):
for j in range(1, k + 1):
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1])
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1])
return dp[n][k][0]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
for i in range(k + 1):
dp[1][i][1] = -prices[0]
for i in range(2, n + 1):
for j in range(1, k + 1):
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1])
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1])
return dp[n][k][0]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n + 1)]
dp[1][1] = -prices[0]
for i in range(2, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i - 1])
return dp[n][0]
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n + 1)]
dp[1][1] = -prices[0]
for i in range(2, n + 1):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1])
return dp[n][0]
https://leetcode.com/problems/maximum-subarray-sum-after-one-operation/
class Solution:
def maxSumAfterOperation(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 2 for _ in range(n + 1)]
dp[1][0] = nums[0]
dp[1][1] = nums[0] ** 2
ans = dp[1][1]
for i in range(2, n + 1):
dp[i][0] = max(0, dp[i - 1][0]) + nums[i - 1]
dp[i][1] = max(dp[i - 1][1] + nums[i - 1], max(0, dp[i - 1][0]) + nums[i - 1] ** 2)
ans = max(ans, dp[i][1])
return ans
https://leetcode.com/problems/greatest-sum-divisible-by-three/
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 3 for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = -inf
dp[0][2] = -inf
for i in range(1, n + 1):
if nums[i - 1] % 3 == 0:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1])
elif nums[i - 1] % 3 == 1:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1])
else:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1])
return dp[n][0]
https://leetcode.com/problems/count-ways-to-build-good-strings/
class Solution:
def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
MOD = 10 ** 9 + 7
ans = 0
dp = [0] * 100005
dp[0] = 1
for i in range(1, high + 1):
if i >= zero: dp[i] = dp[i] + dp[i - zero]
if i >= one: dp[i] = dp[i] + dp[i - one]
if i >= low: ans = ans + dp[i]
return ans % MOD
https://leetcode.com/problems/longest-palindromic-substring/
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
x, y = 0, 0
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
if i - j > y - x:
x, y = j, i
return s[x: y + 1]
https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/
class Solution:
def maxPalindromes(self, s: str, k: int) -> int:
n = len(s)
t = []
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[i] == s[j] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
if i - j + 1 >= k: t.append([j, i])
ans = 0
r = -inf
for x, y in t:
if x > r:
r = y
ans += 1
else:
r = min(r, y)
return ans
https://leetcode.com/problems/palindromic-substrings/
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
ans = 0
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
ans += 1
return ans
https://leetcode.com/problems/palindrome-partitioning-iv/
class Solution:
def checkPartitioning(self, s: str) -> bool:
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[j] == s[i] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
for i in range(1, n - 1):
for j in range(i + 1, n):
if dp[0][i - 1] and dp[i][j - 1] and dp[j][n - 1]:
return True
return False
https://leetcode.com/problems/palindrome-partitioning/
class Solution:
def partition(self, s: str) -> List[List[str]]:
def dfs(u, path):
if u == n:
ans.append(path[:])
for i in range(u, n):
if dp[u][i]:
dfs(i + 1, path + [s[u: i + 1]])
n = len(s)
dp = [[False] * n for _ in range(n)]
for i in range(n):
for j in range(i, -1, -1):
if s[i] == s[j] and (i - j <= 2 or dp[j + 1][i - 1]):
dp[j][i] = True
ans = []
dfs(0, [])
return ans
https://leetcode.com/problems/longest-palindromic-subsequence/
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][i] = 1
for i in range(n + 1):
for j in range(i - 1, 0, -1):
if s[j - 1] == s[i - 1]:
dp[j][i] = dp[j + 1][i - 1] + 2
else:
dp[j][i] = max(dp[j][i - 1], dp[j + 1][i])
print(dp)
return dp[1][n]
https://leetcode.com/problems/valid-palindrome-iii/
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
for j in range(i - 1, 0, -1):
if s[j - 1] == s[i - 1]:
dp[j][i] = dp[j + 1][i - 1]
else:
dp[j][i] = min(dp[j + 1][i], dp[j][i - 1]) + 1
return dp[1][n] <= k
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
for j in range(i - 1, 0, -1):
if s[j - 1] == s[i - 1]:
dp[j][i] = dp[j + 1][i - 1]
else:
dp[j][i] = min(dp[j + 1][i], dp[j][i - 1]) + 1
return dp[1][n]
https://leetcode.com/problems/maximize-palindrome-length-from-subsequences/
class Solution:
def longestPalindrome(self, word1: str, word2: str) -> int:
ans = 0
s = word1 + word2
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][i] = 1
for i in range(n + 1):
for j in range(i - 1, 0, -1):
if s[j - 1] == s[i - 1]:
dp[j][i] = dp[j + 1][i - 1] + 2
if j <= len(word1) and i > len(word1): ans = max(ans, dp[j][i])
else:
dp[j][i] = max(dp[j + 1][i], dp[j][i - 1])
return ans
https://leetcode.com/problems/longest-increasing-subsequence/
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for x in nums:
p = bisect_left(dp, x)
if p == len(dp): dp.append(x)
else: dp[p] = x
return len(dp)
https://leetcode.com/problems/increasing-triplet-subsequence/
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
dp = []
for x in nums:
p = bisect_left(dp, x)
if p == len(dp): dp.append(x)
else: dp[p] = x
return len(dp) >= 3
https://leetcode.com/problems/number-of-longest-increasing-subsequence/
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
cnt = [1] * (n + 1)
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
elif dp[j] + 1 == dp[i]:
cnt[i] += cnt[j]
mx = max(dp)
return sum(cnt[i] for i in range(n) if dp[i] == mx)
https://leetcode.com/problems/russian-doll-envelopes/
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key = lambda x: (x[0], -x[1]))
dp = []
for x in envelopes:
l, r = 0, len(dp)
while l < r:
mid = (l + r) // 2
if dp[mid][1] >= x[1]: r = mid
else: l = mid + 1
if l == len(dp): dp.append(x)
else: dp[l] = x
return len(dp)
https://leetcode.com/problems/maximum-length-of-pair-chain/
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key = lambda x: (x[1], x[0]))
dp = []
for x in pairs:
if not dp or dp[-1][1] < x[0]: dp.append(x)
return len(dp)
https://leetcode.com/problems/edit-distance/
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): dp[i][0] = i
for i in range(1, n + 1): dp[0][i] = i
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
return dp[m][n]
https://leetcode.com/problems/maximum-length-of-repeated-subarray/
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
ans = 0
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
ans = max(ans, dp[i][j])
return ans
https://leetcode.com/problems/longest-common-subsequence/
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m = len(text1)
n = len(text2)
dp = [[ 0 for j in range(n + 1) ] for i in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
https://leetcode.com/problems/shortest-common-supersequence/
class Solution:
def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
ans = []
i, j = m, n
while i >= 1 and j >= 1:
if dp[i][j] == dp[i - 1][j]:
ans.append(str1[i - 1])
i -= 1
elif dp[i][j] == dp[i][j - 1]:
ans.append(str2[j - 1])
j -= 1
else:
ans.append(str1[i - 1])
i -= 1
j -= 1
while i >= 1:
ans.append(str1[i - 1])
i -= 1
while j >= 1:
ans.append(str2[j - 1])
j -= 1
return ''.join(ans[::-1])
https://leetcode.com/problems/delete-operation-for-two-strings/
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return m + n - 2 * dp[m][n]
https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
class Solution:
def minimumDeleteSum(self, s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1): dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
for j in range(1, n + 1): dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j] + ord(s1[i - 1]), dp[i][j - 1] + ord(s2[j - 1]))
return dp[m][n]
https://leetcode.com/problems/uncrossed-lines/
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if nums1[i - 1] == nums2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
https://leetcode.com/problems/max-dot-product-of-two-subsequences/
class Solution:
def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
dp = [[-inf] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1], nums1[i - 1] * nums2[j - 1])
return dp[m][n]
https://leetcode.com/problems/interleaving-string/
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
m, n = len(s1), len(s2)
if m + n != len(s3): return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(m + 1):
for j in range(n + 1):
if i > 0 and s1[i - 1] == s3[i + j - 1]:
dp[i][j] |= dp[i - 1][j]
if j > 0 and s2[j - 1] == s3[i + j - 1]:
dp[i][j] |= dp[i][j - 1]
return dp[m][n]
https://leetcode.com/problems/distinct-subsequences/
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if i >= j:
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
class Solution:
def numWays(self, words: List[str], target: str) -> int:
MOD = 10 ** 9 + 7
m, n = len(words[0]), len(target)
cnt = [[0] * 26 for i in range(m)]
for word in words:
for i in range(m):
cnt[i][ord(word[i]) - ord('a')] += 1
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if cnt[i - 1][ord(target[j - 1]) - ord('a')]:
dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * cnt[i - 1][ord(target[j - 1]) - ord('a')] + dp[i - 1][j]) % MOD
else:
dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD
return dp[m][n]
https://leetcode.com/problems/coin-change/
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], dp[i - c] + 1)
return dp[-1] if dp[-1] != inf else -1
https://leetcode.com/problems/coin-change-ii/
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for i in range(c, amount + 1):
dp[i] += dp[i - c]
return dp[-1]
https://leetcode.com/problems/partition-equal-subset-sum/
class Solution:
def canPartition(self, nums: List[int]) -> bool:
@cache
def dp(u, s):
if u == len(nums):
return s == tol // 2
if s > tol // 2: return False
return dp(u + 1, s + nums[u]) or dp(u + 1, s)
tol = sum(nums)
if tol % 2 == 1: return False
return dp(0, 0)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1: return False
tol = sum(nums)
if tol % 2 == 1: return False
V = tol // 2
dp = [False] * (V + 1)
dp[0] = True
for x in nums:
for i in range(V, x - 1, -1):
dp[i] |= dp[i - x]
return dp[V]
https://leetcode.com/problems/target-sum/
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
n = len(nums)
tol = sum(nums)
if tol < target or (tol - target) % 2 == 1: return 0
V = (tol - target) // 2
dp = [0] * (V + 1)
dp[0] = 1
for x in nums:
for i in range(V, x - 1, -1):
dp[i] += dp[i - x]
return dp[V]
https://leetcode.com/problems/last-stone-weight-ii/
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
tol = sum(stones)
V = tol // 2
dp = [0] * (V + 1)
for x in stones:
for i in range(V, x - 1, -1):
dp[i] = max(dp[i], dp[i - x] + x)
return tol - 2 * dp[V]
https://leetcode.com/problems/ones-and-zeroes/
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
zero, one = 0, 0
for c in s:
if c == '0':
zero += 1
else:
one += 1
for i in range(m, zero - 1, -1):
for j in range(n, one - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)
return dp[m][n]
https://leetcode.com/problems/split-array-with-same-average/
class Solution:
def splitArraySameAverage(self, nums: List[int]) -> bool:
@cache
def dp(u, cnt, sm):
if cnt == 0: return sm == 0
if sm < 0 or u + cnt > n: return False
return dp(u + 1, cnt - 1, sm - nums[u]) or dp(u + 1, cnt, sm)
n = len(nums)
tol = sum(nums)
for i in range(1, (n // 2) + 1):
if tol * i % n == 0 and dp(0, i, tol * i // n): return True
return False
https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/
class Solution:
def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
dp = set(mat[0])
for i in range(1, len(mat)):
nxt = set()
for x in mat[i]:
for pre in dp:
nxt.add(x + pre)
dp = nxt
return min(abs(x - target) for x in dp)
https://leetcode.com/problems/triangle/
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
for i in range(1, n):
for j in range(i + 1):
triangle[i][j] += min(triangle[i - 1][j] if i != j else inf, triangle[i - 1][j - 1] if j != 0 else inf)
return min(triangle[-1])
https://leetcode.com/problems/minimum-falling-path-sum/
class Solution:
def minFallingPathSum(self, matrix: List[List[int]]) -> int:
n = len(matrix)
for i in range(1, n):
for j in range(n):
t = inf
if j - 1 >= 0: t = min(t, matrix[i - 1][j - 1])
t = min(t, matrix[i - 1][j])
if j + 1 < n: t = min(t, matrix[i - 1][j + 1])
matrix[i][j] += t
return min(matrix[-1])
https://leetcode.com/problems/minimum-falling-path-sum-ii/
class Solution:
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
for i in range(1, n):
l, r = grid[i - 1][:], grid[i - 1][:]
for j in range(1, n): l[j] = min(l[j], l[j - 1])
for j in range(n - 2, -1, -1): r[j] = min(r[j], r[j + 1])
for j in range(n):
grid[i][j] += min(l[j - 1] if j != 0 else inf, r[j + 1] if j != n - 1 else inf)
return min(grid[-1])
https://leetcode.com/problems/out-of-boundary-paths/
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
@cache
def dp(i, j, k):
if not (0 <= i < m and 0 <= j < n): return 1
if k == 0: return 0
ans = 0
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
ans = (ans + dp(ni, nj, k - 1)) % MOD
return ans
MOD = 10 ** 9 + 7
return dp(startRow, startColumn, maxMove)
https://leetcode.com/problems/cherry-pickup/
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
@cache
def dp(i, j, x, y):
if i == j == n - 1: return grid[i][j]
cur = grid[i][j] + grid[x][y]
if i == x and j == y: cur //= 2
ans = -inf
for ni, nj in [(i + 1, j), (i, j + 1)]:
if ni < n and nj < n and grid[ni][nj] != -1:
for nx, ny in [(x + 1, y), (x, y + 1)]:
if nx < n and ny < n and grid[nx][ny] != -1:
ans = max(ans, cur + dp(ni, nj, nx, ny))
return ans
n = len(grid)
return max(0, dp(0, 0, 0, 0))