| Problem Names | Solution Writeups | Code |
|---|---|---|
| Climbing Stairs |
stairs[n] = stairs[n-1] + stairs[n-2]. Create storage that stores each stairs[n] to increase the speed with tradeoff of O(n) extra space. |
|
| Min Cost Climbing Stairs |
Trick is to add one more cost with value=0, and then for each level we update cost value to cost[i] = min(cost[i-1], cost[i-2]) + cost[i]. cost[len(cost)-1] will be the answer. |
|
| House Robber |
Create two variables that store previous max and current max. Update current max to (nums[i] + previous max) if that is greater. |
|
| House Robber II |
Key idea is house[0] and house[n-1] cannot be stolen together, so break the problem into compare two profits from stealing from house[0] to house[n-2] and house[1] to house[n-1]. |
|
| Longest Palindromic Substring |
Instead of Compare boundary characters, another way to check if a string is palindrome is starting at the middle character, and then expand out (left and right pointers) to see if a string is palindrome (s[left] == s[right]). To also cater even length palindrome, do another check with left = i, right = i + 1. |
|
| Palindromic Substrings |
Same trick, starts palindromic checking at middle character, and then count++ whenever it is a palindrome. |
|
| Maximum Product Subarray |
Keep track of current min and current max, when current number is negative, swap current max and current min. |
|
| Decode Ways |
Core idea is dp[i] = dp[i+1] + dp[i+2] and dp[len(s)] = 1 since empty string has 1 decode way. dp[i+2] is neccessary only if the two-digits number is within 10-26. Starts from dp[len(s)-1] and then dp[0] is the answer. |
|
| Coin Change |
Greedy does not work! Create an array with size amount+1 calls dp. The idea is that dp[amt] = 1 + dp[amt-coin] for each coin, and store only the minimum. Then, dp[amount] will be the answer. If dp[amount] is the default value, return -1. |
|
| Word Break |
For dynamic programming solution, dp[i] = dp[i + len(word)] for each word in wordDict. If dp[i] is true, break the loop immediately. Return dp[0] at the end. |
|
| Longest Increasing Subsequence |
Start from the last element, for each number that is after the element, if that number > current element, update dp[current] to dp[number] + 1. After completing this loop, find the max in dp. |
|
| Partition Equal Subset Sum |
The equal sum value must be sum(nums) // 2, if sum(nums) is odd, simply return false. Else, create a set dp, for each number in nums, can choose between add and don't add, if don't add then it will be add 0. Check also if target is in sum. If yes simply return true, else return false. |