Created python template for diffrent DP patterns as mentioned in the below mentioned post:
https://leetcode.com/discuss/general-discussion/662866/Dynamic-Programming-for-Practice-Problems-Patterns-and-Sample-Solutions
There can be more optimized version of the solution available but you can use this as tempate, tweak it and solve problems which have similar patterns
1. Longest Increasing Subsequence variants:
Problem Used: https://leetcode.com/problems/longest-increasing-subsequence/
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1] * len(nums)
for i in range(1,len(nums)):
for j in range(0,i):
if nums[i] > nums[j]:
dp[i] = max(dp[j]+1,dp[i])
return max(dp)2. Partition Subset:
Problem Used: https://leetcode.com/problems/partition-equal-subset-sum/
class Solution:
def canPartition(self, arr: List[int]) -> bool:
sub_sum = 0
sub_sum = sum(arr)
if sub_sum % 2 != 0: return False
s,n = (sub_sum//2) + 1,len(arr) + 1
dp = [[False for i in range(s)] for j in range(n)]
for i in range(n):
for j in range(s):
if i == 0:
dp[i][j] = False
if j == 0:
dp[i][j] = True
for i in range(1,n):
for j in range(1,s):
if j >= arr[i-1]:
dp[i][j] = dp[i-1][j] or dp[i-1][j-arr[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[-1][-1]3. BitMasking:
post: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/335668/DP-with-Bit-Masking-Solution-%3A-Best-for-Interviews
Problem Used: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
4. Longest Common Subsequence Variant:
Problem Used: https://leetcode.com/problems/longest-common-subsequence/
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [[0 for i in range(len(text1)+1)] for j in range(len(text2)+1)]
for i in range(1,len(text2)+1):
for j in range(1,len(text1)+1):
if text2[i-1] == text1[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[-1][-1]5. Palindrome:
Problem Used:
6. Coin Change variant:
Problem Used: https://leetcode.com/problems/coin-change/
import sys
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [[-1 for i in range(amount+1)] for j in range(len(coins)+1)]
for i in range(len(coins)+1):
for j in range(amount+1):
if j == 0:
dp[i][j] = 0
if i == 0:
dp[i][j] = sys.maxsize - 1
for i in range(1,len(coins)+1):
for j in range(1,amount+1):
if coins[i-1] <= j:
dp[i][j] = min(dp[i-1][j] , dp[i][j - coins[i-1]] + 1)
else:
dp[i][j] = dp[i-1][j]
if dp[-1][-1] == sys.maxsize - 1:
return -1
else:
return dp[-1][-1]
7. Matrix multiplication variant:
Problem Used: https://leetcode.com/problems/minimum-score-triangulation-of-polygon/submissions/
class Solution:
def minScoreTriangulation(self, A: List[int]) -> int:
n = len(A)
dp = [[0]*n for i in range(n)]
for i in range(2, n):
for left in range(0, n - i):
right = left + i
dp[left][right] = float("Inf")
for k in range(left + 1, right):
dp[left][right] = min(dp[left][right], dp[left][k] + dp[k][right] + A[left]*A[right]*A[k])
return dp[0][-1]8. Matrix/2D Array:
Problem Used:
9. Hash + DP:
Problem Used:
10. State machine:
Problem Used : 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:
sell, buy = 0, -float(inf)
for i in range(len(prices)):
sell_old = sell
sell = max(sell, buy + prices[i] - fee)
buy = max(buy, sell_old - prices[i])
return sell11. Depth First Search + DP:
Problem Used: https://leetcode.com/problems/knight-probability-in-chessboard/
class Solution:
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
memo = {}
dir=[[-2,-1],[-1,-2],[1,-2],[2,-1],[2,1],[1,2],[-1,2],[-2,1]]
def solve(K,i,j,p):
if(i < 0 or i > N - 1 or j < 0 or j > N - 1):
return 0
if K <= 0:
return p
valid = 0
for x,y in dir:
if (i+x,j+y,K) not in memo:
memo[(i+x,j+y,K)] = solve(K-1,i+x,j+y,p/8)
valid += memo[(i+x,j+y,K)]
return valid
return solve(K,r,c,1)12. Minimax DP:
Problem Used:
Will keep on updating the remaing patterns