---
# System prepended metadata

title: Dynamic Programming

---

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]
```