LeetCode 70 – Climbing Stairs
Distinct ways to climb n stairs (1 or 2 steps).
dp[i] = dp[i-1] + dp[i-2].
Base: dp[0]=1, dp[1]=1.
Space optimize with two vars.
O(n) time, O(1) space.
Tag: Fibonacci DP.
LeetCode 746 – Min Cost Climbing Stairs
Min cost to reach top (pay cost[i] when step on i).
dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
Answer = min(dp[n-1], dp[n-2]).
Space O(1).
Tag: DP on steps.
LeetCode 198 – House Robber
Max money w/o robbing adjacent houses.
dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Initialize dp[0]=nums[0], dp[1]=max(nums[0],nums[1]).
Space optimize with two vars.
Tag: DP, Choose/Skip.
LeetCode 213 – House Robber II
Like #198 but houses in a circle.
Break into two cases: [0..n-2] and [1..n-1].
Run House Robber on both, take max.
Tag: DP on circle, subproblem split.
LeetCode 5 – Longest Palindromic Substring
Longest palindrome in s.
Expand Around Center O(n²) or DP table:
dp[l][r]=true if s[l]==s[r] && (r-l<3 || dp[l+1][r-1]).
Track longest.
Tag: 2-pointer center or DP.
LeetCode 647 – Palindromic Substrings
Count all palindromic substrings.
Expand around every center (2n-1) counting valid palindromes.
Or DP like #5 but count instead of max.
O(n²) time.
Tag: DP / Expand center.
LeetCode 91 – Decode Ways
Count ways to decode digits to letters.
dp[i] = (s[i-1]!=’0’? dp[i-1] : 0) + (valid two-digit? dp[i-2] : 0).
Base: dp[0]=1.
O(n) time, O(1) space.
Tag: DP on string.
LeetCode 322 – Coin Change
Fewest coins to make amount.
dp[0]=0; for a in [1..amount], dp[a]=1+min(dp[a-c]).
Init dp with ∞.
O(n*amount).
Tag: Unbounded knap, Bottom-up.
LeetCode 152 – Maximum Product Subarray
Largest product of contiguous subarray.
Track curMax, curMin (negatives swap).
At each num: update max(num, numprevMax, numprevMin) and min similarly.
Keep global best.
O(n) time, O(1) space.
Tag: DP, min/max trick.
LeetCode 139 – Word Break
Can s be segmented into dict words?
dp[i] true if ∃ word w in dict where s[i-len(w):i]==w && dp[i-len(w)].
Init dp[0]=true.
O(n²) time.
Tag: DP on prefix, HashSet.
LeetCode 300 – LIS
Length of longest increasing subsequence.
DP O(n²): dp[i]=1+max(dp[j]|j<i & nums[j]<nums[i]).
Optimize O(n log n): patience sorting w/ tails array + binary search.
Tag: DP or Greedy+BS.
LeetCode 416 – Partition Equal Subset Sum
Can nums be split into 2 equal-sum subsets?
Target = sum/2 (if odd → false).
0/1 knapsack: dp[x]=true if x reachable.
Iterate nums: for val in [target..val] desc: dp[val] |= dp[val-num].
O(n*sum/2).
Tag: DP on subset sums.
