# **程式筆記(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
```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階
```
```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為止) 字符串所有可能的組成方式數目
如果可以單個存在，就把上一項加起來，如果可以雙個存在，就把前前一項加起來
```
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這個數字前的組合數量
```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加上自己
```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
```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，後用公式去一步一步更新到最上面
```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永遠是儲存走到這步的最佳解
```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`
Sign in with Wallet
Connect another wallet