All DP problems with categorization

Hi All,

I just completed my DP adventure which I started in last June and I would like to share my findings in this post. There are total 241 dp tagged problems in LeetCode as of Today, and 26 of them are locked so I only solved the public ones.

• First of all, I participated the monthly challenge April & May, so this really helped me to build a habbit of daily problem solving

• Then I started solving DP problems and updating my monthly problem list here. https://leetcode.com/discuss/general-discussion/665187/everyday-dp-challenge-list

• The average pace was about 1 problem per day.

• I read these great articles to learn the general dynamic programming knowledge & patterns https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns https://leetcode.com/discuss/general-discussion/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions

The followings are my categorization of the all 215 DP problems. (In each category, problems are sorted by LeetCode difficulty) Table version of the list: https://chuka231.blogspot.com/2021/01/leetcode-all-dynamic-programming.html

Linear DP

https://leetcode.com/problems/climbing-stairs/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ https://leetcode.com/problems/min-cost-climbing-stairs/ https://leetcode.com/problems/divisor-game/ https://leetcode.com/problems/decode-ways/ https://leetcode.com/problems/unique-binary-search-trees/ https://leetcode.com/problems/house-robber/ https://leetcode.com/problems/perfect-squares/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ https://leetcode.com/problems/coin-change/ https://leetcode.com/problems/counting-bits/ https://leetcode.com/problems/integer-break/ https://leetcode.com/problems/count-numbers-with-unique-digits/ https://leetcode.com/problems/wiggle-subsequence/ https://leetcode.com/problems/partition-equal-subset-sum/ https://leetcode.com/problems/maximum-length-of-pair-chain/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ https://leetcode.com/problems/delete-and-earn/ https://leetcode.com/problems/domino-and-tromino-tiling/ https://leetcode.com/problems/knight-dialer/ https://leetcode.com/problems/minimum-cost-for-tickets/ https://leetcode.com/problems/partition-array-for-maximum-sum/ https://leetcode.com/problems/filling-bookcase-shelves/ https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/ https://leetcode.com/problems/greatest-sum-divisible-by-three/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ https://leetcode.com/problems/student-attendance-record-ii/ https://leetcode.com/problems/decode-ways-ii/ https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero/ https://leetcode.com/problems/maximum-profit-in-job-scheduling/ https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/ https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/ https://leetcode.com/problems/stone-game-iii/ https://leetcode.com/problems/restore-the-array/ https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/ https://leetcode.com/problems/stone-game-iv/ https://leetcode.com/problems/coin-change-2/

Knapsack

https://leetcode.com/problems/house-robber-ii/ https://leetcode.com/problems/ones-and-zeroes/ https://leetcode.com/problems/target-sum/ https://leetcode.com/problems/shopping-offers/ https://leetcode.com/problems/2-keys-keyboard/ https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/ https://leetcode.com/problems/best-team-with-no-conflicts/ https://leetcode.com/problems/profitable-schemes/ https://leetcode.com/problems/tallest-billboard/ https://leetcode.com/problems/pizza-with-3n-slices/ https://leetcode.com/problems/reducing-dishes/

Multi Dimension DP

https://leetcode.com/problems/triangle/ https://leetcode.com/problems/combination-sum-iv/ https://leetcode.com/problems/out-of-boundary-paths/ https://leetcode.com/problems/knight-probability-in-chessboard/ https://leetcode.com/problems/champagne-tower/ https://leetcode.com/problems/largest-sum-of-averages/ https://leetcode.com/problems/minimum-falling-path-sum/ https://leetcode.com/problems/video-stitching/ https://leetcode.com/problems/longest-arithmetic-subsequence/ https://leetcode.com/problems/stone-game-ii/ https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ https://leetcode.com/problems/dice-roll-simulation/ https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/ https://leetcode.com/problems/create-maximum-number/ https://leetcode.com/problems/frog-jump/ https://leetcode.com/problems/split-array-largest-sum/ https://leetcode.com/problems/freedom-trail/ https://leetcode.com/problems/minimum-number-of-refueling-stops/ https://leetcode.com/problems/number-of-music-playlists/ https://leetcode.com/problems/count-vowels-permutation/ https://leetcode.com/problems/minimum-falling-path-sum-ii/ https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/ https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/ https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/ https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/ https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/ https://leetcode.com/problems/paint-house-iii/ https://leetcode.com/problems/count-all-possible-routes/

Interval DP

https://leetcode.com/problems/guess-number-higher-or-lower-ii/ https://leetcode.com/problems/arithmetic-slices/ https://leetcode.com/problems/predict-the-winner/ https://leetcode.com/problems/palindromic-substrings/ https://leetcode.com/problems/stone-game/ https://leetcode.com/problems/minimum-score-triangulation-of-polygon/ https://leetcode.com/problems/last-stone-weight-ii/ https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/ https://leetcode.com/problems/stone-game-vii/ https://leetcode.com/problems/burst-balloons/ https://leetcode.com/problems/remove-boxes/ https://leetcode.com/problems/strange-printer/ https://leetcode.com/problems/valid-permutations-for-di-sequence/ https://leetcode.com/problems/minimum-cost-to-merge-stones/ https://leetcode.com/problems/allocate-mailboxes/ https://leetcode.com/problems/minimum-cost-to-cut-a-stick/ https://leetcode.com/problems/stone-game-v/

Bit DP

https://leetcode.com/problems/can-i-win/ https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ https://leetcode.com/problems/stickers-to-spell-word/ https://leetcode.com/problems/shortest-path-visiting-all-nodes/ https://leetcode.com/problems/smallest-sufficient-team/ https://leetcode.com/problems/maximum-students-taking-exam/ https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/ https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/ https://leetcode.com/problems/maximum-number-of-achievable-transfer-requests/ https://leetcode.com/problems/distribute-repeating-integers/ https://leetcode.com/problems/maximize-grid-happiness/ https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/

Digit DP

https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/ https://leetcode.com/problems/numbers-at-most-n-given-digit-set/ https://leetcode.com/problems/numbers-with-repeated-digits/

DP on Trees

https://leetcode.com/problems/unique-binary-search-trees-ii/ https://leetcode.com/problems/house-robber-iii/ https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/ https://leetcode.com/problems/linked-list-in-binary-tree/ https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/ https://leetcode.com/problems/binary-tree-cameras/ https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/ https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/

String DP

https://leetcode.com/problems/is-subsequence/ https://leetcode.com/problems/palindrome-partitioning/ https://leetcode.com/problems/palindrome-partitioning-ii/ https://leetcode.com/problems/word-break/ https://leetcode.com/problems/unique-substrings-in-wraparound-string/ https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/ https://leetcode.com/problems/longest-string-chain/ https://leetcode.com/problems/longest-happy-string/ https://leetcode.com/problems/longest-valid-parentheses/ https://leetcode.com/problems/distinct-subsequences/ https://leetcode.com/problems/word-break-ii/ https://leetcode.com/problems/count-the-repetitions/ https://leetcode.com/problems/concatenated-words/ https://leetcode.com/problems/count-different-palindromic-subsequences/ https://leetcode.com/problems/distinct-subsequences-ii/ https://leetcode.com/problems/longest-chunked-palindrome-decomposition/ https://leetcode.com/problems/palindrome-partitioning-iii/ https://leetcode.com/problems/find-all-good-strings/ https://leetcode.com/problems/string-compression-ii/ https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/

Probability DP

https://leetcode.com/problems/soup-servings/ https://leetcode.com/problems/new-21-game/ https://leetcode.com/problems/airplane-seat-assignment-probability/

Classic DPs

Cadane's Algorithm

https://leetcode.com/problems/maximum-subarray/ https://leetcode.com/problems/maximum-product-subarray/ https://leetcode.com/problems/bitwise-ors-of-subarrays/ https://leetcode.com/problems/longest-turbulent-subarray/ https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ https://leetcode.com/problems/k-concatenation-maximum-sum/ https://leetcode.com/problems/largest-divisible-subset/ https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

LCS

https://leetcode.com/problems/longest-palindromic-substring/ https://leetcode.com/problems/longest-palindromic-subsequence/ https://leetcode.com/problems/maximum-length-of-repeated-subarray/ https://leetcode.com/problems/longest-common-subsequence/ https://leetcode.com/problems/regular-expression-matching/ https://leetcode.com/problems/wildcard-matching/ https://leetcode.com/problems/edit-distance/ https://leetcode.com/problems/interleaving-string/ https://leetcode.com/problems/shortest-common-supersequence/ https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/ https://leetcode.com/problems/max-dot-product-of-two-subsequences/

LIS

https://leetcode.com/problems/longest-increasing-subsequence/ https://leetcode.com/problems/number-of-longest-increasing-subsequence/ https://leetcode.com/problems/russian-doll-envelopes/ https://leetcode.com/problems/delete-columns-to-make-sorted-iii/ https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/ https://leetcode.com/problems/maximum-height-by-stacking-cuboids/ https://leetcode.com/problems/make-array-strictly-increasing/

2D Grid Traversal

https://leetcode.com/problems/unique-paths/ https://leetcode.com/problems/unique-paths-ii/ https://leetcode.com/problems/minimum-path-sum/ https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/ https://leetcode.com/problems/where-will-the-ball-fall/ https://leetcode.com/problems/dungeon-game/ https://leetcode.com/problems/cherry-pickup/ https://leetcode.com/problems/number-of-paths-with-max-score/ https://leetcode.com/problems/cherry-pickup-ii/ https://leetcode.com/problems/kth-smallest-instructions/

Cumulative Sum

https://leetcode.com/problems/range-sum-query-immutable/ https://leetcode.com/problems/maximal-square/ https://leetcode.com/problems/range-sum-query-2d-immutable/ https://leetcode.com/problems/largest-plus-sign/ https://leetcode.com/problems/push-dominoes/ https://leetcode.com/problems/largest-1-bordered-square/ https://leetcode.com/problems/count-square-submatrices-with-all-ones/ https://leetcode.com/problems/matrix-block-sum/ https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/ https://leetcode.com/problems/count-submatrices-with-all-ones/ https://leetcode.com/problems/ways-to-make-a-fair-array/ https://leetcode.com/problems/maximal-rectangle/ https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/ https://leetcode.com/problems/super-washing-machines/ https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/ https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/ https://leetcode.com/problems/get-the-maximum-score/

Hashmap (SubArray)

https://leetcode.com/problems/continuous-subarray-sum/ https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/ https://leetcode.com/problems/maximum-number-of-non-overlapping-subarrays-with-sum-equals-target/

DP + Alpha(Tricks/DS)

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/ https://leetcode.com/problems/odd-even-jump/ https://leetcode.com/problems/constrained-subsequence-sum/ https://leetcode.com/problems/delivering-boxes-from-storage-to-ports/

Insertion DP

https://leetcode.com/problems/k-inverse-pairs-array/

Graph DP

https://leetcode.com/problems/cheapest-flights-within-k-stops/ https://leetcode.com/problems/find-the-shortest-superstring/

Memoization

https://leetcode.com/problems/minimum-jumps-to-reach-home/ https://leetcode.com/problems/scramble-string/ https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/ https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/ https://leetcode.com/problems/jump-game-v/ https://leetcode.com/problems/minimum-number-of-days-to-eat-n-oranges/

Binary Lifting

https://leetcode.com/problems/kth-ancestor-of-a-tree-node/

Math

https://leetcode.com/problems/ugly-number-ii/ https://leetcode.com/problems/count-sorted-vowel-strings/ https://leetcode.com/problems/race-car/ https://leetcode.com/problems/super-egg-drop/ https://leetcode.com/problems/least-operators-to-express-number/ https://leetcode.com/problems/largest-multiple-of-three/ https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/

References:

• Solved all dynamic programming (dp) problems in 7 months. - LeetCode Discuss