# **程式筆記(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
```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
```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股票
```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`
Sign in with Wallet
Connect another wallet