LeetCode DP(Dynamic Programming)

leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months

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

 

 

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 challange April & May, so this really helped me to build a habbit of daily problem solving
• Then I started to solve DP problems and kept 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)

1.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/

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/

3.Multi Dimensions 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/

4.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/

5.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/

6.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/

7.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/

8.String DP

https://leetcode.com/problems/is-subsequence/
https://leetcode.com/problems/palindrome-partitioning/
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/

9.Probability DP

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

10.Classic DPs

A.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/

B.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/

C.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/

D.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/

E.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/

F.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/

11.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/

12.Insertion DP

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

13.Graph DP

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

14.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/

15.Binary Lifting

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

16.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/