---
# System prepended metadata

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

---

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


:::info
:information_source: 日期 : 2023/02/24
:::


**:thumbsup:Dynamic Programming(DP)** 

DP 適用於解決重疊子問題，通過記錄中間結果來避免重複計算

Divide and Conquer 適用處理獨立的子問題，將問題拆解成更小的不重複子問題，逐步解決，最後合併結果 

Bottom-Up - 從最簡單的子問題開始 / 迴圈
Top-Down - memoization 記錄已解決的子問題結果 / 遞迴
    

**:thumbsup:DP(bottom-up + 一維陣列 + 和前兩項有關)**


* Unique Paths
![image](https://hackmd.io/_uploads/SkQVWgI60.png =40%x)

```python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        return dp[-1][-1]
```


* Climbing Stairs爬梯子(1 or 2階)
類似fibonacci
```
dp[i - 1] 加上 1階
dp[i - 2] 加上 2階
```
![image](https://hackmd.io/_uploads/ryBaS39gJl.png =50%x)

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] 
        return dp[n]
```
* Min Cost Climbing Stairs (走樓梯)
現在這個位置的代價 = min(前面兩個 (當下的代價 + 累加的代價))
dp : 累加的代價 the cost before i location
cost : 當前的代價 the cost on i location
```python
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)

        for i in range(2, n + 1):
            dp[i] = min(cost[i - 1] + dp[i - 1], cost[i - 2] + dp[i - 2])
        
        return dp[n]
```

* Decode Ways(數字字母組成)
dp[i]代表 解析s (從起頭到目前的i為止) 字符串所有可能的組成方式數目
如果可以單個存在，就把上一項加起來，如果可以雙個存在，就把前前一項加起來
![image](https://hackmd.io/_uploads/SJhyyeSIa.png =70%x)

```
dp[i] = dp[i] + dp[i - 1] 如果介於0 ~ 10
dp[i] = dp[i] + dp[i - 2] 如果介於10 ~ 26
```

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, n + 1):
            c = int(s[i - 1])
            if 0 < c <= 9:
                dp[i] = dp[i - 1]
            if i > 1:
                pre_c = int(s[i - 2])
                if 10 <= (pre_c * 10 + c) <= 26:
                    dp[i] += dp[i - 2]

        return dp[n]
```


**:thumbsup:DP(bottom-up + 一維陣列 + 數量)**

用一維陣列即可，因為我們關注的是這個dp[i]的數量
計算關於"組成某個amount" / "最長序列" / "組成某一個sum"


* Coin Change
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0

        for a in range(amount + 1):
            for c in coins:
                if a >= c:
                    dp[a] = min(dp[a], dp[a - c] + 1)

        return dp[amount] if dp[amount] != float("inf") else -1
```

* combination Sum IV(數字組合)
dp[i]為 i這個數字累積到現在的排列組合量
dp[i] += dp[i - n]，加上n這個數字前的組合數量
![image](https://hackmd.io/_uploads/Bkv8clTna.png =70%x)

```python
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(1, target + 1):
            for n in nums:
                if i >= n:
                    dp[i] += dp[i - n]
        
        return dp[target]
```


* Longest Increasing Subsequence(最長遞增序列)
dp[i]的意義為 到i這個數字為止 最長的遞增數列
dp[j] + 1 -> 前面小數字j加上自己
![image](https://hackmd.io/_uploads/B1U4jg62T.png =70%x)


```python
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n

        for i in range(n):
            for j in range(0, i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)
```


* Perfect Squares
find least number of perfect square numbers(1, 4, 9, 16 ..) that sum to n
時間複雜度O(n * sqar(n))
```python
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [n] * (n + 1)
        dp[0] = 0

        largest_root = int(pow(n, 0.5)) # 需要找的最大平方根
        # 紀錄平方根count
        for root in range(1, largest_root + 1):
            square = root ** 2
            dp[square] = 1

        for i in range(n + 1):
            for root in range(1, largest_root + 1):
                square = root ** 2
                if i >= square:
                    dp[i] = min(dp[i], dp[i - square] + 1) # 只嘗試用square組成
        return dp[n]
```


**:thumbsup:DP(bottom-up + 一維陣列)**

* Word Break(worddict中的字是否能組成給定字串)
```
s = “catsandog”
wordDict = [“cats”,“dog”,“sand”,“and”,“cat”]
每個一一去對照(每一個word都要跑)
**catsandog
TFFTTFFTFF**
```
```python
dp[i]代表 (從起頭到目前的i為止) wordDict中的word有能力組合到i這個位置
特定項 -> 給定的word並且可以和s相對應
s[i : i + n] == word
```
```python
class Solution(object):
    def wordBreak(self, s, wordDict):
        n = len(s)
        record = [False] * (n + 1)
        record[0] = True

        for i in range(n):
            for w in wordDict:
                wlen = len(w)
                if i + wlen <= n and w == s[i : i + wlen] and record[i]:
                    record[i + wlen] = True

        return record[n]
```


* Pascal's Triangle
![image](https://hackmd.io/_uploads/SkwVwQF3p.png =30%x)

```python
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = [[1], [1, 1]]
        if numRows == 1:
            return [res[0]]
        if numRows == 2:
            return res
        
        for r in range(3, numRows + 1):
            temp = [1] * r
            for i in range(1, r - 1):
                temp[i] = res[-1][i - 1] + res[-1][i]
            res.append(temp)
        
        return res 
```




**:thumbsup:DP(House Robber)**
* House Robber房屋搶劫

1. 常數
```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])

        # initialize
        pre, cur = nums[0], max(nums[0], nums[1])
        
        for i in range(2, n):
            temp = max(nums[i] + pre, cur)
            pre = cur
            cur = temp
        
        return cur
```

2. top down + memoization
類似dfs但有儲存功能，樹會高度重複
先從0開始，一路travese到最下面，得到一個base case是0，後用公式去一步一步更新到最上面
![image](https://hackmd.io/_uploads/BJilNFyCC.pn =70%x)

```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        memo = [0] * n
        visited = set()

        def traverse(i):
            # base case for 4 and 5
            if i >= n:
                return 0
            # already calculate the tree
            if i in visited:
                return memo[i]

            res = max(nums[i] + traverse(i + 2), traverse(i + 1))
            memo[i] = res
            visited.add(i)

            return res
        
        traverse(0)

        return memo[0]
```

3. bottom-up
dp[1]是取max(nums[0], nums[1])
dp永遠是儲存走到這步的最佳解
![image](https://hackmd.io/_uploads/B1lbTFyAR.png =70%x)

```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        if n == 1:
            return nums[0]
        if n == 2:
            return max(nums[0], nums[1])

        # initialize
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        for i in range(2, n):
            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
        
        return dp[n - 1]
```

* 房屋搶劫(二)
既然第一個和最後一個不能同時被搶，那就分別算0 ~ n - 1 和 1 ~ n 區間，並且比較回傳大的
```python
max( self.maxRob(0, len(nums) - 1, nums),
     self.maxRob(1, len(nums), nums) )
```

---




**講解連結**

Provided by. 

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