1-D Dynamic Programming
Dynamic programming is "don't solve the same question twice". Break a problem into smaller versions of itself, solve each small version once and write down the answer. In 1-D problems the state is a single index: "the best answer for the first i items".
After this topic: You can define dp[i] in words, write the transition, find the base case and then compress the space.
Do these first: Backtracking
Step 1 · Read the lesson
Break a problem into overlapping subproblems and solve each only once.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
- 1.Climbing StairsEasy
To reach step n you came from step n−1 or n−2. So how many ways in total?
ways(n) = ways(n−1) + ways(n−2); iterate keeping only the last two values.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func climbStairs(n int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// ClimbStairs: ways to reach step n taking 1 or 2 steps at a time. // Bottom-up with O(1) space: dp[i] only needs dp[i-1] and dp[i-2]. func ClimbStairs(n int) int { prev, cur := 1, 1 // ways to reach step 0 and step 1 for i := 2; i <= n; i++ { prev, cur = cur, prev+cur } return cur } - 2.Min Cost Climbing StairsEasy
Cheapest cost to stand on step i depends on the two steps below it.
dp[i] = cost[i] + min(dp[i−1], dp[i−2]); the answer is min of the last two.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func minCostClimbingStairs(cost []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// MinCostClimbingStairs: you may start on step 0 or 1; the top is just past the last step. // State: cost to stand on step i = cost[i] + the cheaper of the two steps you could have come from. func MinCostClimbingStairs(cost []int) int { a, b := 0, 0 // cheapest cost to reach the two most recent steps (starting is free) for i := 2; i <= len(cost); i++ { a, b = b, min(b+cost[i-1], a+cost[i-2]) } return b } - 3.House RobberMedium
At each house you either rob it (and skip the previous) or skip it.
dp[i] = max(dp[i−1], dp[i−2] + nums[i]); keep two variables.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func rob(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// Rob: max loot from a row of houses, never two adjacent. // State: best loot using houses[0..i]. Transition: skip house i, or take it + best up to i-2. func Rob(nums []int) int { take, skip := 0, 0 // best if we may use the previous house / best up to two houses ago for _, v := range nums { take, skip = max(skip+v, take), take } return take } - 4.House Robber IIMedium
The street is a circle, so house 0 and house n−1 are neighbours. Break the circle.
Run House Robber twice — on houses [0..n−2] and [1..n−1] — and take the max (plus the n=1 special case).
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func rob(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// RobCircle: houses form a circle, so the first and last cannot both be robbed. // Solve the line twice (without the last house, then without the first) and take the better one. func RobCircle(nums []int) int { if len(nums) == 1 { return nums[0] } return max(Rob(nums[:len(nums)-1]), Rob(nums[1:])) } - 5.Longest Palindromic SubstringMedium
Every palindrome has a centre. How many possible centres are there?
For each of the 2n−1 centres expand outward while the characters match; keep the longest.
Target: O(n²) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func longestPalindrome(s string) stringTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// LongestPalindrome: every palindrome has a centre, and there are 2n-1 centres // (n letters and n-1 gaps between letters). Expand outward from each while the ends match. func LongestPalindrome(s string) string { start, length := 0, 0 expand := func(l, r int) { for l >= 0 && r < len(s) && s[l] == s[r] { l-- r++ } if r-l-1 > length { start, length = l+1, r-l-1 } } for i := range s { expand(i, i) // odd length, centred on a letter expand(i, i+1) // even length, centred between two letters } return s[start : start+length] } // CountSubstrings: the same expansion, counting every success instead of keeping the longest. func CountSubstrings(s string) int { count := 0 expand := func(l, r int) { for l >= 0 && r < len(s) && s[l] == s[r] { count++ l-- r++ } } for i := range s { expand(i, i) expand(i, i+1) } return count } - 6.Palindromic SubstringsMedium
Same centre-expansion idea, but count every successful expansion.
Expand around each centre (odd and even) and add 1 for every palindrome found.
Target: O(n²) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func countSubstrings(s string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// LongestPalindrome: every palindrome has a centre, and there are 2n-1 centres // (n letters and n-1 gaps between letters). Expand outward from each while the ends match. func LongestPalindrome(s string) string { start, length := 0, 0 expand := func(l, r int) { for l >= 0 && r < len(s) && s[l] == s[r] { l-- r++ } if r-l-1 > length { start, length = l+1, r-l-1 } } for i := range s { expand(i, i) // odd length, centred on a letter expand(i, i+1) // even length, centred between two letters } return s[start : start+length] } // CountSubstrings: the same expansion, counting every success instead of keeping the longest. func CountSubstrings(s string) int { count := 0 expand := func(l, r int) { for l >= 0 && r < len(s) && s[l] == s[r] { count++ l-- r++ } } for i := range s { expand(i, i) expand(i, i+1) } return count } - 7.Decode WaysMedium
The last one digit or the last two digits form a letter. When is each valid?
dp[i] = (s[i−1] ≠ "0" ? dp[i−1] : 0) + (10 ≤ two-digit ≤ 26 ? dp[i−2] : 0), with dp[0]=1.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func numDecodings(s string) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// NumDecodings: "12" can be "AB" (1,2) or "L" (12). // dp[i] = ways to decode the first i digits = (last digit alone is 1-9) + (last two digits are 10-26). func NumDecodings(s string) int { if len(s) == 0 || s[0] == '0' { return 0 } prev2, prev1 := 1, 1 // ways for 0 digits and for 1 digit for i := 2; i <= len(s); i++ { cur := 0 if s[i-1] != '0' { cur += prev1 } if two := int(s[i-2]-'0')*10 + int(s[i-1]-'0'); two >= 10 && two <= 26 { cur += prev2 } prev2, prev1 = prev1, cur } return prev1 } - 8.Coin ChangeMedium
The fewest coins for amount a = 1 + the fewest coins for (a − some coin).
dp[0]=0; dp[a] = 1 + min(dp[a−c]) over coins c ≤ a; unreachable stays at infinity.
Target: O(amount · coins) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func coinChange(coins []int, amount int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// CoinChange: fewest coins that make up amount, or -1. // State: dp[a] = fewest coins for amount a. Order: small amounts first. func CoinChange(coins []int, amount int) int { inf := amount + 1 // larger than any real answer dp := make([]int, amount+1) for a := 1; a <= amount; a++ { dp[a] = inf for _, c := range coins { if c <= a { dp[a] = min(dp[a], dp[a-c]+1) } } } if dp[amount] >= inf { return -1 } return dp[amount] } - 9.Maximum Product SubarrayMedium
A very negative product can become the biggest after one more negative number. What two values must you track?
Track both the max and min product ending at each index; a negative number swaps them.
Target: O(n) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func maxProduct(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// MaxProduct: a negative number can flip the smallest product into the largest, // so track BOTH the max and the min product of a subarray ending here. func MaxProduct(nums []int) int { best, hi, lo := nums[0], nums[0], nums[0] for _, n := range nums[1:] { a, b := hi*n, lo*n hi = max(n, max(a, b)) lo = min(n, min(a, b)) best = max(best, hi) } return best } - 10.Word BreakMedium
Can the prefix of length i be built? It can if some earlier prefix can AND the piece in between is a word.
dp[0]=true; dp[i] = any j < i with dp[j] and s[j:i] in the dictionary.
Target: O(n² · L) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func wordBreak(s string, wordDict []string) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// WordBreak: can s be split into dictionary words? // dp[i] = the first i letters can be split, true when some earlier cut j works AND s[j:i] is a word. func WordBreak(s string, words []string) bool { dict := make(map[string]bool, len(words)) for _, w := range words { dict[w] = true } dp := make([]bool, len(s)+1) dp[0] = true for i := 1; i <= len(s); i++ { for j := 0; j < i; j++ { if dp[j] && dict[s[j:i]] { dp[i] = true break } } } return dp[len(s)] } - 11.Longest Increasing SubsequenceMedium
Define the best sequence that ends exactly at position i. Which earlier elements can it extend?
dp[i] = 1 + max(dp[j]) for j<i with nums[j] < nums[i] (O(n²)); or keep a "tails" array and binary-search it (O(n log n)).
Target: O(n²), improvable to O(n log n)
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func lengthOfLIS(nums []int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// LengthOfLIS: length of the longest strictly increasing subsequence. // State: dp[i] = best length ending exactly at nums[i]. func LengthOfLIS(nums []int) int { best := 0 dp := make([]int, len(nums)) for i := range nums { dp[i] = 1 for j := 0; j < i; j++ { if nums[j] < nums[i] { dp[i] = max(dp[i], dp[j]+1) } } best = max(best, dp[i]) } return best } - 12.Partition Equal Subset SumMedium
It is possible only if you can pick numbers that add up to exactly half of the total.
Subset-sum DP: reachable[0]=true; for each number update sums from the target down to the number (descending so each number is used once).
Target: O(n · sum/2) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func canPartition(nums []int) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Dynamic Programming lesson page.
// CanPartition: split into two subsets with equal sums = can some numbers reach exactly half? // reachable[s] means "some chosen numbers add up to s". Loop DOWNWARDS so each number is used once. func CanPartition(nums []int) bool { total := 0 for _, n := range nums { total += n } if total%2 != 0 { return false } half := total / 2 reachable := make([]bool, half+1) reachable[0] = true for _, n := range nums { for s := half; s >= n; s-- { reachable[s] = reachable[s] || reachable[s-n] } } return reachable[half] }