# Dynamic Programming Study Guide
:::warning
[< Return to Home Page](https://hackmd.io/@siansiansu/HknJJm0W0)
:::
Basic DP Problems
-----------------
Fundamental problems that introduce the concept of dynamic programming.
- 🟩 [70\. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) \[[Solution](https://hackmd.io/@siansiansu/SkmoRqDfR)\]
- 🟩 [509\. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) \[[Solution](https://hackmd.io/@siansiansu/SkqozRb70)\]
- 🟩 [746\. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) \[[Solution](https://hackmd.io/@siansiansu/ryootTjM0)\]
Matrix Path Problems
--------------------
Problems involving finding optimal paths through a matrix.
- 🟨 [64\. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) \[[Solution](https://hackmd.io/@siansiansu/SytGJ0sf0)\]
- 🟨 [120\. Triangle](https://leetcode.com/problems/triangle/) \[[Solution](https://hackmd.io/@siansiansu/SkitU-Cf0)\]
- 🟨 [931\. Minimum Falling Path Sum](https://leetcode.com/problems/minimum-falling-path-sum/) \[[Solution](https://hackmd.io/@siansiansu/rkyR2ynfR)\]
Counting Paths in a 2D Array
----------------------------
Problems that involve counting the number of possible paths.
- 🟨 [62\. Unique Paths](https://leetcode.com/problems/unique-paths/) \[[Solution](https://hackmd.io/@siansiansu/S1UpB0-X0)\]
- 🟨 [63\. Unique Paths II](https://leetcode.com/problems/unique-paths-ii/) \[[Solution](https://hackmd.io/@siansiansu/rkBoFppQC)\]
Substring and Subsequence Problems
----------------------------------
Problems involving finding or manipulating substrings and subsequences.
- 🟨 [516\. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/) [[Solution]()]
- 🟨 [647\. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/) [[Solution]()]
- 🟧 [1143\. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/) \[[Solution](https://hackmd.io/@siansiansu/rJPWCFh4C)\]
Knapsack Problems
-----------------
A class of problems involving optimizing a selection of items under constraints.
- 🟨 [279\. Perfect Squares](https://leetcode.com/problems/perfect-squares/) \[[Solution](https://hackmd.io/@siansiansu/SyeOyZ6zR)\]
- 🟨 [322\. Coin Change](https://leetcode.com/problems/coin-change/) \[[Solution](https://hackmd.io/@siansiansu/ByuFvknGC)\]
- 🟨 [416\. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)
- 🟨 [474\. Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/) \[[Solution](https://hackmd.io/@siansiansu/r1NZGl2MC)\]
- 🟨 [494\. Target Sum](https://leetcode.com/problems/target-sum/) \[[Solution](https://hackmd.io/@siansiansu/r1hAvCkE0)\]
- 🟨 [518\. Coin Change II](https://leetcode.com/problems/coin-change-ii/)
String Matching and Decoding
----------------------------
Problems involving string manipulation and decoding.
- 🟨 [91\. Decode Ways](https://leetcode.com/problems/decode-ways/) \[[Solution](https://hackmd.io/@siansiansu/HkqxZjifC)\]
- 🟨 [97\. Interleaving String](https://leetcode.com/problems/interleaving-string/)
Time Series Problems
--------------------
Problems that involve sequences of data points in time order.
- 🟨 [198\. House Robber](https://leetcode.com/problems/house-robber/) \[[Solution](https://hackmd.io/@siansiansu/S13tDeMXA)\]
- 🟨 [213\. House Robber II](https://leetcode.com/problems/house-robber-ii/) \[[Solution](https://hackmd.io/@siansiansu/H10kvgI4R)\]
- 🟨 [983\. Minimum Cost For Tickets](https://leetcode.com/problems/minimum-cost-for-tickets/) \[[Solution](https://hackmd.io/@siansiansu/rklPPAizR)\]
### Stock Trading Problems
A subset of time series problems focusing on stock trading scenarios.
- 🟩 [121\. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) \[[Solution](https://hackmd.io/@siansiansu/HJJ7LrPz0)\]
- 🟨 [122\. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) \[[Solution](https://hackmd.io/@siansiansu/BJgms2ONR)\]
- 🟥 [123\. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) \[[Solution](https://hackmd.io/@siansiansu/B1_SY-1wC)\]
- 🟥 [188\. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/) \[[Solution](https://hackmd.io/@siansiansu/B1kutrgw0)\]
- 🟨 [309\. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
- 🟨 [714\. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
Maximum Subarray Problems
-------------------------
Problems involving finding subarrays with maximum sum or product.
- 🟨 [53\. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) \[[Solution](https://hackmd.io/@siansiansu/B1smyX84C)\]
- 🟨 [152\. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) \[[Solution](https://hackmd.io/@siansiansu/H1ljhQI40)\]
- 🟨 [918\. Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/) \[[Solution](https://hackmd.io/@siansiansu/BySRpJDV0)\]
Edit Distance Problems
----------------------
Problems involving calculating the minimum number of operations to transform one string into another.
- 🟥 [72\. Edit Distance](https://leetcode.com/problems/edit-distance/) \[[Solution](https://hackmd.io/@siansiansu/BkF_Eb1rC)\]
- 🟨 [583\. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)
- 🟨 [712\. Minimum ASCII Delete Sum for Two Strings](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/)
Keyboard Problems
-----------------
Problems involving simulating keyboard operations.
- 🟨 [650\. 2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/) \[[Solution](https://hackmd.io/@siansiansu/Bk_9pRhf0)\]
- 🟨 [651\. 4 Keys Keyboard](https://leetcode.com/problems/4-keys-keyboard/)
Matrix Area Problems
--------------------
Problems involving finding areas or shapes within matrices.
- 🟥 [85\. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)
- 🟨 [221\. Maximal Square](https://leetcode.com/problems/maximal-square/) \[[Solution](https://hackmd.io/@siansiansu/ry2awZAzA)\]
Sequence Problems
-----------------
Problems involving manipulating or analyzing sequences.
- 🟨 [300\. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) \[[Solution](https://hackmd.io/@siansiansu/rykg1GJNA)\]
- 🟥 [1092\. Shortest Common Supersequence](https://leetcode.com/problems/shortest-common-supersequence/)
Problem Difficulty Legend
-------------------------
- 🟩 Easy
- 🟨 Medium
- 🟧 Medium-Hard
- 🟥 Hard
- ⬛ Very Hard
Additional Resources
--------------------
- [Dynamic Programming Patterns](https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns)
- [Grokking Dynamic Programming Patterns for Coding Interviews](https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews)
- [Introduction to Algorithms (CLRS) - Chapter on Dynamic Programming](https://mitpress.mit.edu/books/introduction-algorithms-third-edition)