Dynamic Programming in Python with Tests

Dynamic Programming holds 242 problems (9 Easy, 139 Medium, 94 Hard). Generate any of them into the current directory with lcpy gen -n <number>.

#	Problem	Difficulty	Solution
5	Longest Palindromic Substring	Medium	solution.py
10	Regular Expression Matching	Hard	solution.py
22	Generate Parentheses	Medium	solution.py
32	Longest Valid Parentheses	Hard	solution.py
42	Trapping Rain Water	Hard	solution.py
44	Wildcard Matching	Hard	solution.py
45	Jump Game II	Medium	solution.py
53	Maximum Subarray	Medium	solution.py
55	Jump Game	Medium	solution.py
62	Unique Paths	Medium	solution.py
63	Unique Paths II	Medium	solution.py
64	Minimum Path Sum	Medium	solution.py
70	Climbing Stairs	Easy	solution.py
72	Edit Distance	Hard	solution.py
85	Maximal Rectangle	Hard	solution.py
87	Scramble String	Hard	solution.py
91	Decode Ways	Medium	solution.py
95	Unique Binary Search Trees II	Medium	solution.py
96	Unique Binary Search Trees	Medium	solution.py
97	Interleaving String	Medium	solution.py
115	Distinct Subsequences	Hard	solution.py
118	Pascal’s Triangle	Easy	solution.py
119	Pascal’s Triangle II	Easy	solution.py
120	Triangle	Medium	solution.py
121	Best Time to Buy and Sell Stock	Easy	solution.py
122	Best Time to Buy and Sell Stock II	Medium	solution.py
123	Best Time to Buy and Sell Stock III	Hard	solution.py
124	Binary Tree Maximum Path Sum	Hard	solution.py
131	Palindrome Partitioning	Medium	solution.py
132	Palindrome Partitioning II	Hard	solution.py
139	Word Break	Medium	solution.py
140	Word Break II	Hard	solution.py
152	Maximum Product Subarray	Medium	solution.py
174	Dungeon Game	Hard	solution.py
188	Best Time to Buy and Sell Stock IV	Hard	solution.py
198	House Robber	Medium	solution.py
213	House Robber II	Medium	solution.py
221	Maximal Square	Medium	solution.py
233	Number of Digit One	Hard	solution.py
241	Different Ways to Add Parentheses	Medium	solution.py
256	Paint House	Medium	solution.py
264	Ugly Number II	Medium	solution.py
265	Paint House II	Hard	solution.py
276	Paint Fence	Medium	solution.py
279	Perfect Squares	Medium	solution.py
294	Flip Game II	Medium	solution.py
300	Longest Increasing Subsequence	Medium	solution.py
309	Best Time to Buy and Sell Stock with Cooldown	Medium	solution.py
312	Burst Balloons	Hard	solution.py
313	Super Ugly Number	Medium	solution.py
322	Coin Change	Medium	solution.py
329	Longest Increasing Path in a Matrix	Hard	solution.py
333	Largest BST Subtree	Medium	solution.py
337	House Robber III	Medium	solution.py
338	Counting Bits	Easy	solution.py
343	Integer Break	Medium	solution.py
351	Android Unlock Patterns	Medium	solution.py
354	Russian Doll Envelopes	Hard	solution.py
357	Count Numbers with Unique Digits	Medium	solution.py
361	Bomb Enemy	Medium	solution.py
368	Largest Divisible Subset	Medium	solution.py
375	Guess Number Higher or Lower II	Medium	solution.py
376	Wiggle Subsequence	Medium	solution.py
377	Combination Sum IV	Medium	solution.py
392	Is Subsequence	Easy	solution.py
396	Rotate Function	Medium	solution.py
397	Integer Replacement	Medium	solution.py
403	Frog Jump	Hard	solution.py
410	Split Array Largest Sum	Hard	solution.py
413	Arithmetic Slices	Medium	solution.py
416	Partition Equal Subset Sum	Medium	solution.py
418	Sentence Screen Fitting	Medium	solution.py
435	Non-overlapping Intervals	Medium	solution.py
446	Arithmetic Slices II - Subsequence	Hard	solution.py
458	Poor Pigs	Hard	solution.py
464	Can I Win	Medium	solution.py
465	Optimal Account Balancing	Hard	solution.py
466	Count The Repetitions	Hard	solution.py
467	Unique Substrings in Wraparound String	Medium	solution.py
471	Encode String with Shortest Length	Hard	solution.py
472	Concatenated Words	Hard	solution.py
473	Matchsticks to Square	Medium	solution.py
474	Ones and Zeroes	Medium	solution.py
486	Predict the Winner	Medium	solution.py
487	Max Consecutive Ones II	Medium	solution.py
488	Zuma Game	Hard	solution.py
494	Target Sum	Medium	solution.py
509	Fibonacci Number	Easy	solution.py
514	Freedom Trail	Hard	solution.py
516	Longest Palindromic Subsequence	Medium	solution.py
518	Coin Change II	Medium	solution.py
526	Beautiful Arrangement	Medium	solution.py
542	01 Matrix	Medium	solution.py
546	Remove Boxes	Hard	solution.py
552	Student Attendance Record II	Hard	solution.py
553	Optimal Division	Medium	solution.py
562	Longest Line of Consecutive One in Matrix	Medium	solution.py
568	Maximum Vacation Days	Hard	solution.py
576	Out of Boundary Paths	Medium	solution.py
583	Delete Operation for Two Strings	Medium	solution.py
600	Non-negative Integers without Consecutive Ones	Hard	solution.py
629	K Inverse Pairs Array	Hard	solution.py
634	Find the Derangement of An Array	Medium	solution.py
638	Shopping Offers	Medium	solution.py
639	Decode Ways II	Hard	solution.py
646	Maximum Length of Pair Chain	Medium	solution.py
647	Palindromic Substrings	Medium	solution.py
650	2 Keys Keyboard	Medium	solution.py
651	4 Keys Keyboard	Medium	solution.py
656	Coin Path	Hard	solution.py
664	Strange Printer	Hard	solution.py
673	Number of Longest Increasing Subsequence	Medium	solution.py
678	Valid Parenthesis String	Medium	solution.py
687	Longest Univalue Path	Medium	solution.py
688	Knight Probability in Chessboard	Medium	solution.py
689	Maximum Sum of 3 Non-Overlapping Subarrays	Hard	solution.py
691	Stickers to Spell Word	Hard	solution.py
698	Partition to K Equal Sum Subsets	Medium	solution.py
712	Minimum ASCII Delete Sum for Two Strings	Medium	solution.py
714	Best Time to Buy and Sell Stock with Transaction Fee	Medium	solution.py
718	Maximum Length of Repeated Subarray	Medium	solution.py
727	Minimum Window Subsequence	Hard	solution.py
730	Count Different Palindromic Subsequences	Hard	solution.py
740	Delete and Earn	Medium	solution.py
741	Cherry Pickup	Hard	solution.py
746	Min Cost Climbing Stairs	Easy	solution.py
750	Number Of Corner Rectangles	Medium	solution.py
764	Largest Plus Sign	Medium	solution.py
787	Cheapest Flights Within K Stops	Medium	solution.py
788	Rotated Digits	Medium	solution.py
790	Domino and Tromino Tiling	Medium	solution.py
792	Number of Matching Subsequences	Medium	solution.py
799	Champagne Tower	Medium	solution.py
801	Minimum Swaps To Make Sequences Increasing	Hard	solution.py
805	Split Array With Same Average	Hard	solution.py
808	Soup Servings	Medium	solution.py
813	Largest Sum of Averages	Medium	solution.py
818	Race Car	Hard	solution.py
823	Binary Trees With Factors	Medium	solution.py
828	Count Unique Characters of All Substrings of a Given String	Hard	solution.py
834	Sum of Distances in Tree	Hard	solution.py
837	New 21 Game	Medium	solution.py
838	Push Dominoes	Medium	solution.py
845	Longest Mountain in Array	Medium	solution.py
847	Shortest Path Visiting All Nodes	Hard	solution.py
871	Minimum Number of Refueling Stops	Hard	solution.py
873	Length of Longest Fibonacci Subsequence	Medium	solution.py
877	Stone Game	Medium	solution.py
879	Profitable Schemes	Hard	solution.py
887	Super Egg Drop	Hard	solution.py
894	All Possible Full Binary Trees	Medium	solution.py
898	Bitwise ORs of Subarrays	Medium	solution.py
902	Numbers At Most N Given Digit Set	Hard	solution.py
903	Valid Permutations for DI Sequence	Hard	solution.py
907	Sum of Subarray Minimums	Medium	solution.py
913	Cat and Mouse	Hard	solution.py
918	Maximum Sum Circular Subarray	Medium	solution.py
920	Number of Music Playlists	Hard	solution.py
926	Flip String to Monotone Increasing	Medium	solution.py
931	Minimum Falling Path Sum	Medium	solution.py
935	Knight Dialer	Medium	solution.py
940	Distinct Subsequences II	Hard	solution.py
943	Find the Shortest Superstring	Hard	solution.py
956	Tallest Billboard	Hard	solution.py
960	Delete Columns to Make Sorted III	Hard	solution.py
964	Least Operators to Express Number	Hard	solution.py
968	Binary Tree Cameras	Hard	solution.py
975	Odd Even Jump	Hard	solution.py
978	Longest Turbulent Subarray	Medium	solution.py
979	Distribute Coins in Binary Tree	Medium	solution.py
983	Minimum Cost For Tickets	Medium	solution.py
996	Number of Squareful Arrays	Hard	solution.py
1000	Minimum Cost to Merge Stones	Hard	solution.py
1014	Best Sightseeing Pair	Medium	solution.py
1035	Uncrossed Lines	Medium	solution.py
1043	Partition Array for Maximum Sum	Medium	solution.py
1048	Longest String Chain	Medium	solution.py
1049	Last Stone Weight II	Medium	solution.py
1055	Shortest Way to Form String	Medium	solution.py
1058	Minimize Rounding Error to Meet Target	Medium	solution.py
1092	Shortest Common Supersequence	Hard	solution.py
1105	Filling Bookcase Shelves	Medium	solution.py
1137	N-th Tribonacci Number	Easy	solution.py
1140	Stone Game II	Medium	solution.py
1143	Longest Common Subsequence	Medium	solution.py
1155	Number of Dice Rolls With Target Sum	Medium	solution.py
1162	As Far from Land as Possible	Medium	solution.py
1216	Valid Palindrome III	Hard	solution.py
1220	Count Vowels Permutation	Hard	solution.py
1230	Toss Strange Coins	Medium	solution.py
1235	Maximum Profit in Job Scheduling	Hard	solution.py
1246	Palindrome Removal	Hard	solution.py
1255	Maximum Score Words Formed by Letters	Hard	solution.py
1259	Handshakes That Don’t Cross	Hard	solution.py
1269	Number of Ways to Stay in the Same Place After Some Steps	Hard	solution.py
1277	Count Square Submatrices with All Ones	Medium	solution.py
1289	Minimum Falling Path Sum II	Hard	solution.py
1334	Find the City With the Smallest Number of Neighbors at a Threshold Distance	Medium	solution.py
1335	Minimum Difficulty of a Job Schedule	Hard	solution.py
1359	Count All Valid Pickup and Delivery Options	Hard	solution.py

Pages: 1, 2

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Dynamic Programming in Python with Tests