Idea: Do all the problems that you can. Then collect them together and draw whatever you need.
Problem List extracted
https://leetcode.com/studyplan/dynamic-programming/
- Grab all the problems here (together with the drawings.) and use them to create the pseudocode's later.
- Time it. Try to get them fast.
## Ideas for the future:
- Run experimentation where
## Problems
I
### Fibonacci Number
https://leetcode.com/problems/fibonacci-number/?envType=study-plan-v2&envId=dynamic-programming
3:51
```py
class Solution:
def fib(self, n: int) -> int:
if n==0:
return 0
if n <= 2:
return 1
prev = 1
prev2 = 1
for _ in range(n-2):
temp = prev + prev2
prev2 = prev
prev = temp
return prev
```
### N-th Tribonacci Number
https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming
3:40
```python=
class Solution:
def tribonacci(self, n: int) -> int:
if n ==0:
return 0
elif n<=2:
return 1
prev = 1
prev2 = 1
prev3 = 0
for _ in range(n-2):
res = prev + prev2 + prev3
prev3 = prev2
prev2 = prev
prev = res
return prev
```
### 746. Min Cost Climbing Stairs
https://leetcode.com/problems/min-cost-climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming
```python=
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
prevMin = 0
prevMin2 = 0
for _cost in cost:
res = min(prevMin, prevMin2) + _cost
prevMin2 = prevMin
prevMin = res
return min(prevMin, prevMin2)
```
### 198. House Robber
https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=dynamic-programming
3:45
```python=
class Solution:
def rob(self, nums: List[int]) -> int:
prev = 0
prev2 = 0
for num in nums:
rob = max(prev2 + num, prev)
prev2 = prev
prev = rob
return prev
```
### 740. Delete and Earn
https://leetcode.com/problems/delete-and-earn/description/?envType=study-plan-v2&envId=dynamic-programming
```python
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = {}
for num in nums:
if num not in count:
count[num] = 1
else:
count[num] += 1
sortedNums = list(count.keys())
sortedNums.sort()
for num in range(sortedNums[0], sortedNums[-1]+1):
prevMax = maxes[num-1] if (num-1) in maxes else 0
prev2Max = maxes[num-2] if (num-2) in maxes else 0
if num not in count:
latest = max(prevMax, prev2Max)
else:
latest = max(prevMax, prev2Max + count[num] * num)
maxes[num] = latest
return latest
```
> This one at least a more interesting question here.
Using just prev and prev2
```python
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
count = {}
for num in nums:
if num not in count:
count[num] = 1
else:
count[num] += 1
sortedNums = list(count.keys())
sortedNums.sort()
prev = 0
prev2 = 0
prev = 0
prev2 = 0
for num in range(sortedNums[0], sortedNums[-1] + 1):
if num in count:
current = max(prev, prev2 + count[num] * num)
else:
current = prev
prev2 = prev
prev = current
return prev
```
### 62. Unique Paths
I guess my degree was kindof worth it
https://leetcode.com/problems/unique-paths/?envType=study-plan-v2&envId=dynamic-programming
6:32
```python=
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# This is actually a fun permutation game.
return int(math.factorial(m+n-2) / (math.factorial(m-1) * math.factorial(n-1) ))
```
### 64. Minimum Path Sum
https://leetcode.com/problems/minimum-path-sum/description/?envType=study-plan-v2&envId=dynamic-programming
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
ROWS = len(grid)
COLS = len(grid[0])
minmat = [[0] * COLS for _ in range(ROWS)]
for x in range(COLS):
for y in range(ROWS):
if y==0 and x ==0:
minmat[y][x] = grid[y][x]
elif x == 0:
minmat[y][x] = minmat[y-1][x] + grid[y][x]
elif y == 0:
minmat[y][x] = minmat[y][x-1] + grid[y][x]
else:
minmat[y][x] = min(minmat[y-1][x],
minmat[y][x-1]) + grid[y][x]
return minmat[ROWS-1][COLS-1]
```
Sign in with Wallet
Connect another wallet