---
# System prepended metadata

title: '**程式筆記(dynamic programming + greedy)**'
tags: [code, note, microsoft, dynamic programming]

---

# **程式筆記(dynamic programming + greedy)**


:::info
:information_source: 日期 : 2023/07/21
:::


**:thumbsup:** DP(subarray + greedy)
```
subarray : 是一個陣列中的連續 + 非空元素序列。
```
* Maximum Subarray
想要維持一個連續的subarray，有兩個選擇
1. 前面所有數字 + 當前的數字
2. 捨棄前面數字，只從當前數字開始

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res, temp = float("-inf"), 0
        # 1. choose the (previous + current n)
        # 2. choose the current n
        for n in nums:
            temp = max(temp + n, n)
            res = max(res, temp)
        
        return res
```

**:thumbsup:** DP(Jump Game)

greedy : 永遠關注可以跳到的最大值

* Jump Game(跳躍遊戲)
```
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1,
then 3 steps to the last index.
```
如果可以成功跳過去，就要更新target值因為此時目標已經改變
```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        farest = 0
        
        for i in range(n):
            if i > farest:
                return False
            if nums[i] + i > farest:
                farest = max(farest, nums[i] + i)

        return True
```
```python
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        goal = len(nums) - 1
        for i in range(n - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        
        return True if goal == 0 else False
```

* Jump Game II(跳躍遊戲二)
```
Input: nums = [2,3,1,1,4]
Output: 2
舉例[2,3,1,1,4]，l = r = 0，
第一輪2，可以跳到[3, 1]，最遠最近的index為 l = 1, r = 2
下一輪考慮[3, 1]，可以跳到[1, 4]，最遠最近的index為 l = 3，r = 4
```
用lr去紀錄"可以跳的數字"中，可以跳到的最近和最遠距離(index)
```python
class Solution:
    def jump(self, nums: List[int]) -> int:
        l, r = 0, 0
        step = 0
        n = len(nums)

        for i in range(n):
            # 移到前面 是為了[0] return step = 0 的情況
            if r >= n - 1:
                return step
            maxLen = 0
            for j in range(l, r + 1):
                maxLen = max(maxLen, j + nums[j])
            r = maxLen
            l = i + 1
            step += 1

        return -1
```
* Gas Station(加油站繞行)
greedy : 一旦tank小於0，那就全盤放棄(不可能走到)，重設tank = 0
每個gas station都去嘗試，如果這個station的累加tank小於0，那就全盤放棄累加，因為不可能是這個位置開頭，需要重設accum(tank)為0
![image](https://hackmd.io/_uploads/BkunB0clJg.png =70%x)

```python
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        
        gas_tank, pre_tank = 0, 0
        starting = 0
        for i in range(len(gas)):
            gas_tank += gas[i] - cost[i]
            if gas_tank < pre_tank:
                starting = i + 1
                pre_tank = gas_tank
        
        return starting
```

---



**:thumbsup:** DP(subsequence + greedy + binary search)

* Longest Increasing Subsequence
複雜度為O(nlogn)，binary search 為 round up(回傳l)，希望找到的是res中，比自己大一點的那個數字的index，把它替代成當前數字(較小)時，之後會更有機會找到更長的sequence(greedy)
```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = []
        for i, n in enumerate(nums):
            # binary search 
            ind = self.binary_search_round_up(res, n)

            if ind == len(res): # n is larger than any number
                res.append(n)
            else: # want to replace that large number
            # so that in the future we can find a smaller number
                res[ind] = n
        
        return len(res)
    
    def binary_search_round_up(self, res, n):
        # to find the index of smallest number that is larger than n
        # ex. res = [2, 3, 5], n = 4
        # give back index = 2
        l, r = 0, len(res) - 1

        while l <= r:
            mid = (l + r) // 2
            if n < res[mid]:
                r = mid - 1
            elif n > res[mid]:
                l = mid + 1
            else:
                return mid
        
        return l
```

---



**:thumbsup:** DP(greedy + dict(或其他)紀錄)Memoization

* 號碼牌組堆(Hand of Straights)
**先用dict蒐集，蒐集完後再建立一個minheap**(永遠都會pop當下最小的東西，而且是log(n)複雜度)(使用dict的keys)
**利用minHeap + groupsize找出理想上的數字順序**，當一個dict[數字]為0時，和從minHeap pop出的東西比較，如果不相同則代表錯誤

* 合併triplet去形成目標值(Merge Triplets to Form Target Triplet)
基本上target中的值存在於list中，且該target是幾個"待合併"list中數字最大的，那即為True


* 有效插入字串(Valid Parenthesis String)
**因為有 星星 的加入，故不能單純用左右括號來抵銷，需要創造一個leftmin和leftmax，當 星星 出現時leftmax + 1，leftmin - 1**
1. 當leftmax < 0，最多左括號括號的選項都抵銷不過右括號，必定return False
2. 當leftmin < 0，需要回復成0，因為把太多* 解讀成右括號了，如果leftmax > 0的話，一定有一個狀態是介於兩者之間，完美的處理括號數量
3. 如果leftmin > 0，例如只有一個左括號，必定為錯
```python
leftmin, leftmax = 0, 0

for c in s:
    if c == "(":
        leftmin += 1
        leftmax += 1
    elif c == ")":
        leftmin -= 1
        leftmax -= 1
    else: # c == "*"
        leftmax += 1
        leftmin -= 1

    # ")" is much more than "(" + "*"
    if leftmax < 0:
        return False
    # **() -> treat the * as ""
    # leftmin can both samller or larger than 0 during the calculation
    if leftmin < 0:
        leftmin = 0
# but leftmin has to be zero at the end
# means that they finish 抵銷 left and right
if leftmin == 0:    
    return True 
```
* Remove Duplicate Letters

```python
# when to remove c in stack (s[-1])?
# 1. the c is still available later on
# 2. if remove c can have a better lexico.. result
#    s[-1] > incoming new c

hashmap = {}
for i, c in enumerate(s):
    hashmap[c] = i

stack = []
visited = set()
for i, c in enumerate(s):
    if c in visited:
        continue
    while stack and stack[-1] > c and i < hashmap[stack[-1]]:
        visited.remove(stack[-1])
        stack.pop()
    visited.add(c)
    stack.append(c)

return "".join(stack)
```


---



**:thumbsup:** DP(狀態轉移 + greedy)
* Best Time to Buy and Sell Stock with Transaction Fee
狀態轉移可以觀察從現在這個狀態，可以變到哪些狀態
這題左column沒有箭頭，因為一定要賣了才能再買，所以不能buy到buy
過程中永遠取對大值(greedy)
以下例子transaction fee是2
![image](https://hackmd.io/_uploads/SyvHBtgAA.png =70%x)
```python
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        n = len(prices)
        buy = [0] * n
        sell = [0] * n

        # initialize
        buy[0] = -prices[0]

        for i in range(1, n):
            p = prices[i]
            sell[i] = max(sell[i - 1], buy[i - 1] - fee + p)
            buy[i] = max(buy[i - 1], sell[i - 1] - p)
        
        return max(buy[-1], sell[-1])
```

* Best Time to Buy and Sell Stock with Cooldown
狀態轉移，sold後要強制到reset，held可以選繼續held或sold，reset可以繼續reset或重新hold股票
![image - Copy (8)](https://hackmd.io/_uploads/S1E-Mt5zke.png)
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sold, held, reset = float("-inf"), float("-inf"), 0
        for p in prices:
            pre_sold, pre_held, pre_reset = sold, held, reset
            sold = pre_held + p
            held = max(pre_held, pre_reset - p)
            reset = max(pre_sold, pre_reset)
        
        return max(sold, held, reset)
```

---






**講解連結**

Provided by. me

###### tags: `dynamic programming` `note` `code`