dynamic-programming-problems.md

Dynamic Programming

• Problem listing: https://leetcode.cn/circle/discuss/E3yavq/#%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%AF%87
• Problem listing: https://huxulm.github.io/lc-rating/list/dp

Basic

Problem	Difficulty
509. Fibonacci Number	Easy
279. Perfect Squares	Medium
263. Ugly Number	Easy
264. Ugly Number II	Medium
96. Unique Binary Search Trees	Medium
983. Minimum Cost For Tickets	Medium
1235. Maximum Profit in Job Scheduling	Hard
32. Longest Valid Parentheses	Hard

Climb Stairs

Problem	Difficulty
70. Climbing Stairs	Easy
746. Min Cost Climbing Stairs	Easy
377. Combination Sum IV	Medium
740. Delete and Earn	Medium

House Robber

Problem	Difficulty
198. House Robber	Medium
213. House Robber II	Medium
337. House Robber III	Medium

Maximum Subarray Sum

Problem	Difficulty
53. Maximum Subarray	Medium
152. Maximum Product Subarray	Medium
1749. Maximum Absolute Sum of Any Subarray	Medium (1541)

• https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/description/
• https://leetcode.com/problems/k-concatenation-maximum-sum/description/

Grid

Problem	Difficulty
62. Unique Paths	Medium
63. Unique Paths II	Medium
64. Minimum Path Sum	Medium
221. Maximal Square	Medium

Knapsack

Problem	Difficulty
416. Partition Equal Subset Sum	Medium
494. Target Sum	Medium
279. Perfect Squares	Medium
322. Coin Change	Medium
518. Coin Change 2	Medium
1155. Number of Dice Rolls With Target Sum	Medium

LCS + LIS + Palindrome

Problem	Difficulty
1143. Longest Common Subsequence	Medium
718. Maximum Length of Repeated Subarray	Medium
300. Longest Increasing Subsequence	Medium
673. Number of Longest Increasing Subsequence	Medium
516. Longest Palindromic Subsequence	Medium
5. Longest Palindromic Substring	Medium
647. Palindromic Substrings	Medium

• https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/description/ 1912

Buy and Sell Stock

Problem	Difficulty
121. Best Time to Buy and Sell Stock	Easy
122. Best Time to Buy and Sell Stock II	Medium
123. Best Time to Buy and Sell Stock III	Hard
309. Best Time to Buy and Sell Stock with Cooldown	Medium

劃分型

判定能否划分

Problem	Difficulty	Notes
**139. Word Break	Medium	Iterate each substring, try all possible splits for each substring.

Problem Lists

• https://leetcode.com/discuss/general-discussion/662866/dp-for-beginners-problems-patterns-sample-solutions
• https://leetcode.com/discuss/general-discussion/592146/dynamic-programming-summary
• https://leetcode.com/discuss/general-discussion/1000929/solved-all-dynamic-programming-dp-problems-in-7-months
• https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns