6.9 Exercises
Basic Difficulty
213. House Robber II
Follow-up of the robber problem: how to handle circular arrays?
53. Maximum Subarray
A classic one-dimensional dynamic programming problem. Try optimizing the space complexity to a constant.
343. Integer Break
A partition problem. First, solve it using dynamic programming, then think about whether there's a simpler approach.
583. Delete Operation for Two Strings
A variation of the longest common subsequence problem.
Advanced Difficulty
646. Maximum Length of Pair Chain
A variation of the longest increasing subsequence problem. Similarly, try speeding it up using binary search.
10. Regular Expression Matching
Regex matching is a test of patience. You need to handle different cases, such as characters, asterisks, dots, etc., with careful condition discussions.
376. Wiggle Subsequence
The longest wiggle subsequence has a special formula. Think it through carefully.
494. Target Sum
If told this is a 0-1 knapsack problem, does that give you any ideas?
714. Best Time to Buy and Sell Stock with Transaction Fee
Build a state machine, and stock trading problems will become much easier to solve.