Scribd
Upload
16 views2 pages

Formatted DP Patterns Guide

The document outlines key dynamic programming patterns including Fibonacci, 0/1 Knapsack, and Longest Common Subsequence (LCS). It provides examples of when to use each pattern and includes specific problems from platforms like Leetcode and GFG that exemplify these patterns. The document also includes code snippets for the Fibonacci and LCS patterns.

Uploaded by

hudson daniel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views2 pages

Formatted DP Patterns Guide

The document outlines key dynamic programming patterns including Fibonacci, 0/1 Knapsack, and Longest Common Subsequence (LCS). It provides examples of when to use each pattern and includes specific problems from platforms like Leetcode and GFG that exemplify these patterns. The document also includes code snippets for the Fibonacci and LCS patterns.

Uploaded by

hudson daniel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Dynamic Programming Patterns Cheat Sheet

1. Fibonacci Pattern

When to use: The current value depends on one or two previous values.

# Top-down
memo = {}
def dp(n):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = dp(n-1) + dp(n-2)
return memo[n]

Problems:
- Leetcode 509 - Fibonacci Number
- Leetcode 70 - Climbing Stairs
- Leetcode 746 - Min Cost Climbing Stairs
- Leetcode 198 - House Robber
- Leetcode 213 - House Robber II
- Leetcode 740 - Delete and Earn

2. 0/1 Knapsack Pattern

When to use: Choose or skip elements to maximize/minimize a target sum or value.


Use a 2D table or optimized 1D array.

Problems:
- GFG - Subset Sum Problem
- Leetcode 416 - Partition Equal Subset Sum
- Leetcode 494 - Target Sum
- Leetcode 474 - Ones and Zeroes
- Leetcode 518 - Coin Change II
- Leetcode 322 - Coin Change

3. Longest Common Subsequence (LCS) Pattern

When to use: Compare two strings to find common subsequences or alignments.

# Bottom-up
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] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Problems:
Dynamic Programming Patterns Cheat Sheet

- Leetcode 1143 - Longest Common Subsequence


- Leetcode 115 - Distinct Subsequences
- Leetcode 583 - Delete Operation for Two Strings
- Leetcode 712 - Minimum ASCII Delete Sum
- Leetcode 1035 - Uncrossed Lines
- Leetcode 516 - Longest Palindromic Subsequence

You might also like