Linear DP Problems

5.2 Linear DP Problems

5.2.1 Single Sequence Linear DP Problems

Problem	Title	Solution	Tags	Difficulty
0300	Longest Increasing Subsequence	[[LeetCode XXXX]]	Array, Binary Search, Dynamic Programming	Medium
0673	Number of Longest Increasing Subsequence	[[LeetCode XXXX]]	Binary Indexed Tree, Segment Tree, Array, Dynamic Programming	Medium
0354	Russian Doll Envelopes	[[LeetCode XXXX]]	Array, Binary Search, Dynamic Programming, Sorting	Hard
0053	Maximum Subarray	[[LeetCode XXXX]]	Array, Divide and Conquer, Dynamic Programming	Easy
0152	Maximum Product Subarray	[[LeetCode XXXX]]	Array, Dynamic Programming	Medium
0918	Maximum Sum Circular Subarray	[[LeetCode XXXX]]	Queue, Array, Divide and Conquer, Dynamic Programming, Monotonic Queue	Medium
0198	House Robber	[[LeetCode XXXX]]	Array, Dynamic Programming	Easy
0213	House Robber II	[[LeetCode XXXX]]	Array, Dynamic Programming	Medium
0740	Delete and Earn		Array, Hash Table, Dynamic Programming	Medium
1388	Pizza With 3n Slices		Greedy, Array, Dynamic Programming, Heap (Priority Queue)	Hard
0873	Length of Longest Fibonacci Subsequence	[[LeetCode XXXX]]	Array, Hash Table, Dynamic Programming	Medium
1027	Longest Arithmetic Subsequence		Array, Hash Table, Binary Search, Dynamic Programming	Medium
1055	Shortest Way to Form String		Greedy, Two Pointers, String	Medium
0368	Largest Divisible Subset		Array, Math, Dynamic Programming, Sorting	Medium
0032	Longest Valid Parentheses	[[LeetCode XXXX]]	Stack, String, Dynamic Programming	Hard
0413	Arithmetic Slices		Array, Dynamic Programming	Medium
0091	Decode Ways	[[LeetCode XXXX]]	String, Dynamic Programming	Medium
0639	Decode Ways II	[[LeetCode XXXX]]	String, Dynamic Programming	Hard
0132	Palindrome Partitioning II		String, Dynamic Programming	Hard
1220	Count Vowels Permutation	[[LeetCode XXXX]]	Dynamic Programming	Hard
0338	Counting Bits	[[LeetCode XXXX]]	Bit Manipulation, Dynamic Programming	Medium
0801	Minimum Swaps To Make Sequences Increasing	[[LeetCode XXXX]]	Array, Dynamic Programming	Hard
0871	Minimum Number of Refueling Stops		Greedy, Array, Dynamic Programming, Heap (Priority Queue)	Hard
0045	Jump Game II	[[LeetCode XXXX]]	Greedy, Array, Dynamic Programming	Hard
0813	Largest Sum of Averages		Array, Dynamic Programming, Prefix Sum	Medium
0887	Super Egg Drop	[[LeetCode XXXX]]	Math, Binary Search, Dynamic Programming	Hard
0256	Paint House		Array, Dynamic Programming	Medium
0265	Paint House II		Array, Dynamic Programming	Hard
1473	Paint House III		Array, Dynamic Programming	Hard
0975	Odd Even Jump		Stack, Array, Dynamic Programming, Ordered Set, Monotonic Stack	Hard
0403	Frog Jump	[[LeetCode XXXX]]	Array, Dynamic Programming	Hard
1478	Allocate Mailboxes		Array, Math, Dynamic Programming, Sorting	Hard
1230	Toss Strange Coins		Math, Dynamic Programming, Probability and Statistics	Medium
0410	Split Array Largest Sum	[[LeetCode XXXX]]	Greedy, Array, Binary Search, Dynamic Programming, Prefix Sum	Hard
1751	Maximum Number of Events That Can Be Attended II		Array, Binary Search, Dynamic Programming, Sorting	Hard
1787	Make the XOR of All Segments Equal to Zero		Bit Manipulation, Array, Dynamic Programming	Hard

5.2.2 Dual Sequence Linear DP Problems

Problem	Title	Solution	Tags	Difficulty
1143	Longest Common Subsequence	[[LeetCode XXXX]]	String, Dynamic Programming	Medium
0712	Minimum ASCII Delete Sum for Two Strings		String, Dynamic Programming	Medium
0718	Maximum Length of Repeated Subarray	[[LeetCode XXXX]]	Array, Binary Search, Dynamic Programming, Sliding Window, Hash Function, Rolling Hash	Medium
0583	Delete Operation for Two Strings	[[LeetCode XXXX]]	String, Dynamic Programming	Medium
0072	Edit Distance	[[LeetCode XXXX]]	String, Dynamic Programming	Hard
0044	Wildcard Matching	[[LeetCode XXXX]]	Greedy, Recursion, String, Dynamic Programming	Hard
0010	Regular Expression Matching	[[LeetCode XXXX]]	Recursion, String, Dynamic Programming	Hard
0097	Interleaving String		String, Dynamic Programming	Medium
0115	Distinct Subsequences	[[LeetCode XXXX]]	String, Dynamic Programming	Hard
0085	Maximal Rectangle		Stack, Array, Dynamic Programming, Matrix, Monotonic Stack	Hard

5.2.3 Matrix Linear DP Problems

Problem	Title	Solution	Tags	Difficulty
0118	Pascal's Triangle	[[LeetCode XXXX]]	Array, Dynamic Programming	Easy
0119	Pascal's Triangle II	[[LeetCode XXXX]]	Array, Dynamic Programming	Easy
0120	Triangle	[[LeetCode XXXX]]	Array, Dynamic Programming	Medium
0064	Minimum Path Sum	[[LeetCode XXXX]]	Array, Dynamic Programming, Matrix	Medium
0174	Dungeon Game		Array, Dynamic Programming, Matrix	Hard
0221	Maximal Square	[[LeetCode XXXX]]	Array, Dynamic Programming, Matrix	Medium
0931	Minimum Falling Path Sum		Array, Dynamic Programming, Matrix	Medium
0576	Out of Boundary Paths	[[LeetCode XXXX]]	Dynamic Programming	Medium
0085	Maximal Rectangle		Stack, Array, Dynamic Programming, Matrix, Monotonic Stack	Hard
0363	Max Sum of Rectangle No Larger Than K		Array, Binary Search, Matrix, Ordered Set, Prefix Sum	Hard
1444	Number of Ways of Cutting a Pizza		Memoization, Array, Dynamic Programming, Matrix	Hard

5.2.4 Non-sequence Linear DP Problems

Problem	Title	Solution	Tags	Difficulty
1137	N-th Tribonacci Number	[[LeetCode XXXX]]	Memoization, Math, Dynamic Programming	Easy
0650	2 Keys Keyboard	[[LeetCode XXXX]]	Math, Dynamic Programming	Medium
0264	Ugly Number II	[[LeetCode XXXX]]	Hash Table, Math, Dynamic Programming, Heap (Priority Queue)	Medium
0279	Perfect Squares	[[LeetCode XXXX]]	Breadth-First Search, Math, Dynamic Programming	Medium
0343	Integer Break	[[LeetCode XXXX]]	Math, Dynamic Programming	Medium