DenCT/test-storage / DSA Notes /1D Dynamic Programming.md
DenCT's picture
|
download
raw
23.4 kB
---
tags:
- notes
- dynamic-programming
- 1d-dynamic-programming
patterns:
---
### [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/) EASY
You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?
```
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
```
> [!info] Time and Space Complexity
> You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of steps.
#### Solution
- **Brute Force**
1. Brute force solution is to solve for all possible steps starting from 0, jump 1 or 2 steps.
2. Base case is reaching the step outside the range `n` . When we reach a step beyond or on `n` , return 1 if we are at `n` or 0 if we are beyond `n` . If we are beyond `n` returning 0 indicates that we have reached outside the destination and that that step is invalid.
```python
class Solution:
def climbStairs(self, n: int) -> int:
def helper(i):
if i >= n:
return int(i == n)
return helper(i + 1) + helper(i + 2)
return helper(0)
```
TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$
- **Memoization**
1. Same as brute force, but adding a cache to store the repeating cases
2. Add a cache dictionary to store the distinct ways for each step, and use it when the case is revisited.
```python
class Solution:
def climbStairs(self, n: int) -> int:
cache = {}
def helper(i):
if i >= n:
return int(i == n)
if i in cache:
return cache[i]
cache[i] = helper(i + 1) + helper(i + 2)
return cache[i]
return helper(0)
```
TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$
### [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) EASY
You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index `0`, or the step with index `1`. Return _the minimum cost to reach the top of the floor_.
```
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
```
> [!info] Time and Space Complexity
> You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of steps on the staircase.
#### Solution
- **Brute Force**
1. Using a recursion approach, we can visit all possible steps to check for best minimum cost.
2. We start from 0 and move bottom to reach the final destination. Base case would be when we reach beyond the stairs. In that case, 0 will be returned, indicating that path is not possible.
3. For all other cases, current + 1 and current + 2 steps will be visited and only the minimum of those two will be considered. With that the cost for current step will be added.
4. When the recursion has finished for 0, for 1 the same will be done and the minimum of both will be returned.
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
size = len(cost)
def helper(i):
if i >= size:
return 0
return min(helper(i + 1), helper(i + 2)) + cost[i]
return min(helper(0), helper(1))
```
TIME and SPACE: $O(2^n)$ $O(2^n)$$O(n)$
- **Memoization**
1. Same as above, using recursion to cover all possible steps, but caching the visited steps for reference.
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cache = {}
n = len(cost)
def helper(i):
if i >= n:
return 0
if i in cache:
return cache[i]
cache[i] = min(helper(i + 1), helper(i + 2)) + cost[i]
return cache[i]
return min(helper(0), helper(1))
```
TIME and SPACE: $O(n)$ $O(2^n)$$O(n)$
- **Optimised**
It's an iterative process of starting either from the end or from the beginning and comparing the cost of previous two steps. The answer would be the minimum of latest two prices.
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
size = len(cost)
dp = [0] * (size + 1)
dp[-1], dp[-2] = 0, cost[-1]
for i in range(size - 2, -1, -1):
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]
return min(dp[0], dp[1])
```
**OR**
```python
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
size = len(cost)
dp = [0] * (size + 1)
dp[-1], dp[-2] = 0, cost[-1]
for i in range(size - 2, -1, -1):
dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]
return min(dp[0], dp[1])
```
### [Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/description/) MEDIUM
Given a `m x n` `grid` filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
**Note:** You can only move either down or right at any point in time.
**Example 1:**
![](https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg)
```
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
```
```
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
```
#### Solution
First, we need to create a 2D cache grid to hold the traversal results, and fill it with -1. We start from the bottom right of the grid. Traverse the up and left cell of the bottom right cell, recursively and store the minimum of them in the cache cell in that row and column index. The loop breaking conditions are:
- If the top-left cell is reached, return its value.
- If we reach beyond the grid, return a huge number, indicating we reached beyond the grid.
Lastly, if the cell was already visited, return its value from cache.
```python
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
ROW, COL = len(grid), len(grid[0])
dp = [[-1 for _ in range(COL)] for _ in range(ROW)]
return self.helper(ROW - 1, COL - 1, dp, grid)
def helper(self, i, j, _dp, grid):
if i == 0 and j == 0:
return grid[0][0]
if i < 0 or j < 0:
return 9999999
if _dp[i][j] != -1:
return _dp[i][j]
up = grid[i][j] + self.helper(i - 1, j, _dp, grid)
left = grid[i][j] + self.helper(i, j - 1, _dp, grid)
_dp[i][j] = min(up, left)
return _dp[i][j]
```
Similarly, it can be solved in top-down approach too.
```python
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
ROW, COL = len(grid), len(grid[0])
dp = [[-1 for _ in range(COL)] for _ in range(ROW)]
def helper(i, j):
if i == ROW - 1 and j == COL - 1:
return grid[i][j]
if i >= ROW or j >= COL:
return int(1e9)
if dp[i][j] != -1:
return dp[i][j]
down = grid[i][j] + helper(i + 1, j)
right = grid[i][j] + helper(i, j + 1)
dp[i][j] = min(down, right)
return dp[i][j]
return helper(0, 0)
```
### Coin Change
You are given an integer array `coins` representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer `amount` representing a target amount of money.
Return the fewest number of coins that you need to make up the _exact_ target amount. If it is impossible to make up the amount, return `-1`.
You may assume that you have an unlimited number of each coin.
**Example 1:**
```java
Input: coins = [1,5,10], amount = 12
Output: 3
```
Explanation: 12 = 10 + 1 + 1. Note that we do not have to use every kind coin available.
**Example 2:**
```java
Input: coins = [2], amount = 3
Output: -1
```
Explanation: The amount of 3 cannot be made up with coins of 2.
**Example 3:**
```java
Input: coins = [1], amount = 0
Output: 0
```
Explanation: Choosing 0 coins is a valid way to make up 0
#### Solution
The easiest approach is bottom up DP. We need to have an array of length `amount + 1` to store the no of coins required to sum up to amount `a`, where `a` $\in$ `[1, amount]`. Loop over all possible `a - c` combinations and fill/update the values in the array. For a particular combination of `a - c` the no of coins required to get a sum of `a - c` is `1 + dp[a - c]`. We compare this with existing value of `dp[a- c]` and chose minimum of the two.
> [!info] Time and Space Complexity
> You should aim for a solution with `O(n * t)` time and `O(t)` space, where `n` is the number of coins and `t` is the given amount.
```python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
tabu = [amount + 1] * (amount + 1)
tabu[0] = 0
for a in range(1, amount + 1):
for c in coins:
if a - c >= 0:
tabu[a] = min(tabu[a], 1 + tabu[a - c])
print(tabu)
return tabu[amount] if tabu[amount] != amount + 1 else -1
```
### Edit Distance
You are given two strings `word1` and `word2`, each consisting of lowercase English letters.
You are allowed to perform three operations on `word1` an unlimited number of times:
- Insert a character at any position
- Delete a character at any position
- Replace a character at any position
Return the minimum number of operations to make `word1` equal `word2`.
**Example 1:**
```java
Input: word1 = "monkeys", word2 = "money"
Output: 2
```
Explanation:
`monkeys` -> `monkey` (remove `s`)
`monkey` -> `monkey` (remove `k`)
**Example 2:**
```java
Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3
```
Explanation:
`neatcdee` -> `neetcdee` (replace `a` with `e`)
`neetcdee` -> `neetcde` (remove last `e`)
`neetcde` -> `neetcode` (insert `o`)
#### Solution
![[edit-distance-sol.png]]
We create a 2D grid to store the minimum changes required to get the `word2` string. The size of the grid will be `(len(word1) + 1) * (len(word2) + 1)`. The last row and column of the grid will be the size of the sub-string from that column and row index, indicating that if the one string is empty, it would take "length of the other string" operations to get that string. We do a bottom-up traversal to get the minimum steps required to get the result string. There are two conditions to decide whether to insert, update or delete.
- If the character at the positions are same, it is to be skipped.
- else, the minimum of the 3 operations, insert, delete and update is to be considered and an additional cost is to be added.
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
dp = [[
float("inf") for _ in range(len(word2) + 1)
] for _ in range(len(word1) + 1)
]
for i in range(len(word1) + 1):
dp[i][-1] = len(word1) - i
for i in range(len(word2) + 1):
dp[-1][i] = len(word2) - i
for i in range(len(word1) - 1, -1, -1):
for j in range(len(word2) - 1, -1, -1):
if word1[i] == word2[j]:
dp[i][j] = dp[i + 1][j + 1]
else:
dp[i][j] = min(
dp[i + 1][j],
dp[i][j + 1],
dp[i + 1][j + 1]
) + 1
return dp[0][0]
```
### Decode Ways MEDIUM
A string consisting of uppercase english characters can be encoded to a number using the following mapping:
```java
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
```
To **decode** a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, `"1012"` can be mapped into:
- `"JAB"` with the grouping `(10 1 2)`
- `"JL"` with the grouping `(10 12)`
The grouping `(1 01 2)` is invalid because `01` cannot be mapped into a letter since it contains a leading zero.
Given a string `s` containing only digits, return the number of ways to **decode** it. You can assume that the answer fits in a **32-bit** integer.
**Example 1:**
```java
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
```
**Example 2:**
```java
Input: s = "01"
Output: 0
```
Explanation: "01" cannot be decoded because "01" cannot be mapped into a letter.
#### Solution
Think of decoding as breaking the string into valid 1- or 2-digit groups, each mapping to a letter. Use recursion with memoization: At each step, try decoding 1 digit (if valid) and 2 digits (if between "10"-"26"). Sum up the **ways**, caching results for efficiency.
```python
class Solution:
def numDecodings(self, s: str) -> int:
cache = {len(s):1}
def helper(i):
if i in cache:
return cache[i]
if s[i] == "0":
return 0
res = helper(i + 1)
if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i + 1] in "0123456")):
res += helper(i + 2)
cache[i] = res
return cache[i]
return helper(0)
```
### Maximum Product Subarray MEDIUM
Given an integer array `nums`, find a **subarray** that has the largest product within the array and return it.
A **subarray** is a contiguous non-empty sequence of elements within an array.
You can assume the output will fit into a **32-bit** integer.
**Example 1:**
```java
Input: nums = [1,2,-3,4]
Output: 4
```
**Example 2:**
```java
Input: nums = [-2,-1]
Output: 2
```
#### Solution
We are using Kadane's algorithm here, which is kind of DP and Greedy Algorithm. Loop over each element in the list and calculate the maximum and minimum possible product till that position. Keep a result variable to store the result by modifying it whenever the max product increases.
```python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = nums[0]
curr_min, curr_max = 1, 1
for i, num in enumerate(nums):
temp = curr_max * num
curr_max = max(num * curr_max, num * curr_min, num)
curr_min = min(temp, num * curr_min, num)
res = max(res, curr_max)
return res
```
### Word Break
Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of dictionary words.
You are allowed to reuse words in the dictionary an unlimited number of times. You may assume all dictionary words are unique.
**Example 1:**
```java
Input: s = "neetcode", wordDict = ["neet","code"]
Output: true
```
Explanation: Return true because "neetcode" can be split into "neet" and "code".
**Example 2:**
```java
Input: s = "applepenapple", wordDict = ["apple","pen","ape"]
Output: true
```
Explanation: Return true because "applepenapple" can be split into "apple", "pen" and "apple". Notice that we can reuse words and also not use all the words.
**Example 3:**
```java
Input: s = "catsincars", wordDict = ["cats","cat","sin","in","car"]
Output: false
```
#### Solution
Think of the problem as checking if you can build the string `s` by repeatedly "cutting off" dictionary words from its start. Use dynamic programming:
- Create a boolean array `dp`, where `dp[i]` means "s[i:] can be segmented."
- Start from the end of `s`; at each position, try every word in `wordDict`.
- If a word matches the sub-string at `s[i:]` and the remaining part can be segmented (`dp[i + len(word)]`), mark `dp[i]` as `True`.
- Use early exit to optimize.
This approach efficiently checks all segmentations and avoids recomputation.
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[len(s)] = True
for i in range(len(s) - 1, -1, -1):
for w in wordDict:
if len(s) >= (i + len(w)) and s[i: i + len(w)] == w:
dp[i] = dp[i + len(w)]
if dp[i]:
break
return dp[0]
```
### Longest Increasing Subsequence
Given an integer array `nums`, return the _length_ of the longest strictly _increasing_ subsequence.
A **subsequence** is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.
- For example, `"cat"` is a subsequence of `"crabt"`.
**Example 1:**
```java
Input: nums = [9,1,4,2,3,3,7]
Output: 4
```
Explanation: The longest increasing subsequence is [1,2,3,7], which has a length of 4.
**Example 2:**
```java
Input: nums = [0,3,1,3,2,3]
Output: 4
```
#### Solution
Treat the array as a sequence where for each position `i`, you want to know the length of the longest increasing sub-sequence starting at `i`. Use dynamic programming:
- For each index, look forward to all higher-index elements larger than `nums[i]` and update `dp[i]` accordingly.
- The answer is the maximum in `dp`. This captures all possible sub-sequences efficiently by building solutions for smaller sub-arrays first.
```python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1] * len(nums)
dp[len(nums) - 1] = 1
for i in range(len(nums) - 1, -1, -1):
for j in range(i + 1, len(nums)):
if nums[i] < nums[j]:
dp[i] = max(dp[i], 1 + dp[j])
return max(dp)
```
### **House Robber [Leetcode](https://leetcode.com/problems/house-robber/description/) MEDIUM**
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**. Given an integer array `nums` representing the amount of money of each house, return _the maximum amount of money you can rob tonight **without alerting the police**_.
**Example 1:**
```
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
```
#### Solution
- **Brute Force**
1. Start from the 0th house, move to `i+2` th house or `i+3` th house, chose the max amongst them and add the cost for `i` th house.
2. Base case would be when we have reached the end of list or have reached beyond the list.
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
def helper(i):
if i >= n:
return 0
return max(helper(i + 2), helper(i + 3)) + nums[i]
return max(helper(0), helper(1))
```
- **Optimized (Memoization)**
1. Add a cache dictionary to store visited cases and use them when they are visited again.
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
cache = {}
def helper(i):
if i >= n:
return 0
if i in cache:
return cache[i]
cache[i] = max(helper(i + 2), helper(i + 3)) + nums[i]
return cache[i]
return max(helper(0), helper(1))
```
### House Robber II (Leetcode) MEDIUM
You are given an integer array `nums` where `nums[i]` represents the amount of money the `i`th house has. The houses are arranged in a circle, i.e. the first house and the last house are neighbours. You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were _both_ broken into. Return the _maximum_ amount of money you can rob without alerting the police.
```
Input: nums = [3,4,3]
Output: 4
Input: nums = [2,9,8,3,6]
Output: 15
# Explanation: You cannot rob nums[0] + nums[2] + nums[4] = 16 because nums[0] and nums[4] are adjacent houses. The maximum you can rob is nums[1] + nums[4] = 15.
```
> [!info] Time and Space Complexity
> You should aim for a solution as good or better than `O(n)` time and `O(n)` space, where `n` is the number of houses.
#### Solution
- **Optimized** (**Memoization**)
The circular house constraint means if you rob house 0, you can't rob house n-1, so break this into two linear sub-problems: rob houses 0 to n-2 OR rob houses 1 to n-1. Use a flag parameter to track if house 0 was robbed - when flag = True, you cannot rob the last house. The recursion explores rob/skip decisions at each house while respecting this circular constraint, and the final answer is max(helper(0, True), helper(1, False)) to try both scenarios.
```python
class Solution:
def rob(self, nums: List[int]) -> int:
size = len(nums)
if size == 1:
return nums[size - 1]
cache = {}
def helper(i: int, flag: bool):
if i >= size or (flag and i == size - 1):
return 0
if (i, flag) in cache:
return cache[(i, flag)]
cache[(i, flag)] = max(
helper(i + 1, flag),
helper(i + 2, flag or i == 0) + nums[i],
)
return cache[(i, flag)]
return max(helper(0, True), helper(1, False))
```
### Longest Palindromic Sub-string MEDIUM
Given a string `s`, return the longest sub-string of `s` that is a _palindrome_. A **palindrome** is a string that reads the same forward and backward. If there are multiple palindromic sub-strings that have the same length, return any one of them.
**Example 1:**
```java
Input: s = "ababd"
Output: "bab"
```
Explanation: Both "aba" and "bab" are valid answers.
**Example 2:**
```java
Input: s = "abbc"
Output: "bb"
```
#### Solution
A non-DP solution will be to start from index 0 and spread out, checking all possible palindromes in the string. Then choosing the longest palindrome of them.
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
self.max_string = s[0]
self.max_len = 1
def check_palindrome(i, j):
while i >= 0 and j < len(s) and s[i] == s[j]:
if len(s[i:j + 1]) > self.max_len:
self.max_len = j - i + 1
self.max_string = s[i:j + 1]
i -= 1
j += 1
for i in range(len(s)):
l, r = i, i
check_palindrome(l, r)
l, r = i, i + 1
check_palindrome(l, r)
return self.max_string
```

Xet Storage Details

Size:
23.4 kB
·
Xet hash:
5f5c33ed5c8f806932be15680dccd55abcd6789b169828bc52a585292fa7d592

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.