# Leecode Dynamic Programming
###### tags: `Leetcode`
## [1129 Shortest Path with Alternating Colors](https://leetcode.com/problems/shortest-path-with-alternating-colors/)
Breadth First Search
```python
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
original_path = [[[False, False] for j in range(n)] for i in range(n)]
for edge in red_edges:
original_path[edge[0]][edge[1]][0] = True
for edge in blue_edges:
original_path[edge[0]][edge[1]][1] = True
upper_bound = 2 * n
queue = [(0, 0), (0, 1)]
path = [[upper_bound, upper_bound] for i in range(n)]
visited = [[False, False] for i in range(n)]
path[0][0], path[0][1] = 0, 0
visited[0][0], visited[0][1] = True, True
while queue:
node1, color = queue.pop(0)
if not color and path[node1][0] < upper_bound:
for i, node2 in enumerate(original_path[node1]):
if node2[1] and not visited[i][1]:
queue.append((i, 1))
path[i][1] = path[node1][0] + 1
visited[i][1] = True
if color and path[node1][1] < upper_bound:
for i, node2 in enumerate(original_path[node1]):
if node2[0] and not visited[i][0]:
queue.append((i, 0))
path[i][0] = path[node1][1] + 1
visited[i][0] = True
return [min(i, j) if i < upper_bound or j < upper_bound else -1 for i, j in path]
```
## [1130 Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)
$DP[i,j]=DP[i,k]+DP[k+1,j]+max(A[i:k])\times max(A[k+1:j])$
```python
class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
l = len(arr)
DP = [[0 for j in range(l)] for i in range(l)]
for n in range(l-1, -1, -1):
for i in range(n+1):
j = i + (l - 1 - n)
temp = []
for k in range(i, j):
temp.append(DP[i][k] + DP[k+1][j] + max(arr[i:k+1]) * max(arr[k+1:j+1]))
if temp:
DP[i][j] = min(temp)
return DP[0][l-1]
```
## [3 Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
- 使用一個 hash table `current_pos`儲存每個字元上次出現的位置
- 使用一個與字串`s`相同長度的陣列`longest`儲存若包含當前字元的最長 substring 長度。
- 使用一個迴圈逐步更新陣列`longest`
要考慮的 case 有兩種：
1. 若當前的字元未曾出現過，則將其加入 hash table `current_pos`，長度為前一個字元的 substring 長度 +1
2. 若當前的字元已經出現過，則需要比較上一個字元的 substring 長度 +1 以及與上次出現當前字元的位置的距離，何者較小，並更新 hash table
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
current_pos = {}
longest = [0] * len(s)
for i, c in enumerate(s):
if c not in current_pos:
current_pos[c] = i
longest[i] = longest[i - 1] + 1
else:
longest[i] = min(longest[i - 1] + 1, i - current_pos[c])
current_pos[c] = i
return max(longest)
```
## [5 Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)
1. Brute Force
Time Complexity: $O(n^3)$
Space Complexity: $O(1)$
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
ans = ""
for start in range(len(s)):
for end in range(start, len(s)+1):
new_s = s[start:end]
if new_s[::-1] == new_s and len(new_s) > len(ans):
ans = new_s
return ans
```
2. Dynamic Programming
* Base case: 一個字元、兩個相同的字元
* Incremental case:
* 若一個 string 已經是 palindrome，那麼在其左方及右方再各加上一個相同的字元，則結果依然會是一個 palindrome
* 若一個 string 不是 palindrome，或是在一個是 palindrome 的 string 左右各加上不同的字元，結果都不會是 palindrome
Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]
for i in range(n):
dp[i][i] = True
start = 0
maxlen = 1
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start = i
maxlen = 2
for k in range(3, n+1):
for i in range(n-k+1):
j = i+k-1
if dp[i+1][j-1] and s[i]==s[j]:
dp[i][j] = True
if k > maxlen:
start = i
maxlen = k
return s[start:start+maxlen]
```
較簡化的寫法：
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]
start, end = 0, 0
for i in range(n-1,-1,-1):
for j in range(i, n):
if i == j:
dp[i][j] = True
elif j == i + 1 and s[i] == s[j]:
dp[i][j] = True
elif s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if dp[i][j] and j - i + 1 > end - start + 1:
start, end = i, j
return s[start:end+1]
```
簡化判斷式：$(a\wedge b)\lor(b\wedge c)\implies b\wedge(a\lor c)$
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
dp = [[False for j in range(n)] for i in range(n)]
start, end = 0, 0
for i in range(n-1,-1,-1):
for j in range(i, n):
if (i == j) or (s[i] == s[j]) and (j == i + 1 or dp[i+1][j-1]):
dp[i][j] = True
if dp[i][j] and j - i + 1 > end - start + 1:
start, end = i, j
return s[start:end+1]
```
## 647 Palindromic Substrings
```python
class Solution:
def countSubstrings(self, s: str) -> int:
n = len(s)
DP = [[False for j in range(n)] for i in range(n)]
cnt = 0
for i in range(n-1, -1, -1):
for j in range(i, n):
if i == j:
DP[i][j] = True
elif j == i + 1 and s[i] == s[j]:
DP[i][j] = True
elif s[i] == s[j] and DP[i+1][j-1]:
DP[i][j] = True
cnt += DP[i][j]
return cnt
```
## 516 Longest Palindromic Subsequence
```python
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
DP = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
DP[i][i] = 1
for i in range(n-2, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
DP[i][j] = DP[i+1][j-1] + 2
else:
DP[i][j] = max(DP[i+1][j], DP[i][j-1])
return DP[0][-1]
```
## 931 Minimum Falling Path Sum
來自三個方向的元素：左上、上、右上。
```python
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
x, y = len(A), len(A[0])
DP = [[0 for j in range(y+2)] for i in range(x+1)]
for i in range(1, x+1):
DP[i][0] = DP[i][-1] = 101
for j in range(1, y+1):
DP[i][j] = A[i-1][j-1] + min([DP[i-1][j-1], DP[i-1][j], DP[i-1][j+1]])
return min(DP[-1])
```
in-place 的做法
```python
class Solution:
def minFallingPathSum(self, A: List[List[int]]) -> int:
n = len(A)
for i in range(1, n):
for j in range(0, n):
A[i][j] += min([A[i-1][max(j-1, 0)], A[i-1][j], A[i-1][min(j+1, n-1)]])
return min(A[-1])
```
## 983 Minimum Cost For Tickets
```python
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
DP = [0] * 366
p = 0
for i in range(1, 366):
if days[p] != i:
DP[i] = DP[i-1]
else:
DP[i] = min(DP[i-1]+costs[0], DP[max(i-7,0)]+costs[1], DP[max(i-30,0)]+costs[2])
p += 1
p %= len(days)
return DP[-1]
```
## 413 Arithmetic Slices
原本想用二維的 DP 做，但是無奈 TLE，只能尋求 $O(n)$ 的解法了。
```python
class Solution:
def numberOfArithmeticSlices(self, A: List[int]) -> int:
n = len(A)
diff = [A[i+1] - A[i] for i in range(n-1)]
DP = [0] * n
for i in range(2, n):
if diff[i-1] == diff[i-2]:
DP[i] = DP[i-1] + 1
return sum(DP)
```
## 72 Edit Distance
多花時間理解
```python
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
DP = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0:
DP[i][j] = j
elif j == 0:
DP[i][j] = i
elif word1[i-1] == word2[j-1]:
DP[i][j] = DP[i-1][j-1]
else:
DP[i][j] = 1 + min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1])
return DP[m][n]
```
## 1105 Filling Bookcase Shelves
多花時間理解
```python
class Solution:
def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
n = len(books)
DP = [10000001] * (n+1)
DP[0] = 0
for i in range(1, n+1):
max_height, width_left = 0, shelf_width
for j in range(i-1, -1, -1):
width_left -= books[j][0]
max_height = max(max_height, books[j][1])
if width_left >= 0:
DP[i] = min(max_height + DP[j], DP[i])
return DP[-1]
```
## 1143 Longest Common Subsequence
```python
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n1, n2 = len(text1), len(text2)
DP = [[0 for j in range(n2 + 1)] for i in range(n1 + 1)]
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if text1[i - 1] == text2[j - 1]:
DP[i][j] = DP[i - 1][j - 1] + 1
else:
DP[i][j] = max(DP[i - 1][j], DP[i][j - 1])
return DP[-1][-1]
```
## 714 Best Time to Buy and Sell Stock with Transaction Fee
```python
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
DP = [[0 for j in range(n)] for i in range(n)]
for k in range(n - 1, -1, -1):
for i in range(k + 1):
j = i + n - k - 1
DP[i][j] = max(prices[j] - prices[i] - fee, 0)
for l in range(i, j):
DP[i][j] = max(DP[i][j], DP[i][l] + DP[l + 1][j])
return DP[0][-1]
```
Time Complexity: $O(n^3)$
Space Complexity: $O(n^2)$
很不幸的 TLE。
另個解法：
兩個 state，buy 與 sell：
- `buy[i]`: 第`i`天選擇買入 or 不買入，看哪種方式可獲得最大的 prfit
- 選擇買入: `buy[i]=sell[i-1]-prices[i]-fee`
- 選擇不買入: `buy[i]=buy[i-1]`
- `sell[i]`: 第`i`天選擇賣出 or 不賣出，看哪種方式可獲得最大的 prfit
- 選擇賣出: `sell[i]=buy[i-1]+prices[i]`
- 選擇不賣出: `sell[i]=sell[i-1]`
可以選擇在買入或賣出的時候扣除手續費，這邊選擇在買入的時候計算手續費。
```python
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
buy, sell = [0] * n, [0] * n
buy[0] = -prices[0] - fee
for i in range(1, n):
buy[i] = max(buy[i-1], sell[i-1] - prices[i] - fee)
sell[i] = max(sell[i-1], buy[i-1] + prices[i])
return sell[-1]
```
Time Complexity: $O(n)$
Space Complexity: $O(n)$
## 1027 Longest Arithmetic Sequence
DP with hash table
```python
class Solution:
def longestArithSeqLength(self, A: List[int]) -> int:
n = len(A)
dist = [{} for _ in range(n)]
max_len = 0
for i in range(n):
for j in range(i):
diff = A[i] - A[j]
if diff in dist[j].keys():
dist[i][diff] = dist[j][diff] + 1
else:
dist[j][diff] = 1
dist[i][diff] = 2
max_len = max(max_len, dist[i][diff])
return max_len
```
Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$
## 62 Unique Paths
DP - 2D array
```python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
DP = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
DP[i][0] = 1
for j in range(n):
DP[0][j] = 1
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]
```
Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$
---
DP - 1D array
```python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
DP = [0 for _ in range(n+1)]
DP[1] = 1
for i in range(m):
for j in range(1, n+1):
DP[j] = DP[j-1] + DP[j]
return DP[-1]
```
Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
---
Formula
```python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
return self.f(m+n-2) // (self.f(m-1) * self.f(n-1))
def f(self, n):
if n == 0: return 1
return n * self.f(n-1)
```
Time Complexity: $O(n)$
Space Complexity: $O(1)$
## 64 Minimum Path Sum
```python
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for i in range(1, m):
grid[i][0] += grid[i-1][0]
for j in range(1, n):
grid[0][j] += grid[0][j-1]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]
```
Time Complexity: $O(n^2)$
Space Complexity: $O(1)$
## 96 Unique Binary Search Trees
$G(n)$: 1~n 可以組成幾種 BST
$F(i,n)$: 當 i 在 root 時有幾種 BST 的組合
$G(n)=\sum_{i=1}^{n}F(i,n)$
$F(i,n)=G(i-1)\times G(n-i)$
```python
class Solution:
def numTrees(self, n: int) -> int:
G = [0] * (n + 1)
G[0] = G[1] = 1
for i in range(2, n+1):
for j in range(1, i+1):
G[i] += G[j-1] * G[i-j]
return G[n]
```
Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
## 650 2 Keys Keyboard
```python
class Solution:
def minSteps(self, n: int) -> int:
DP = [0] * (n + 1)
for i in range(2, n+1):
DP[i] = i
for j in range(i-1, 1, -1):
if i % j == 0:
DP[i] = DP[j] + (i // j)
break
return DP[n]
```
## 486 Predict the Winner
```python
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
return self.Score(nums, 0, len(nums) - 1) >= 0
def Score(self, nums, i, j):
if i == j:
return nums[i]
return max(nums[i] - self.Score(nums, i+1, j),
nums[j] - self.Score(nums, i, j-1))
```
```python
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
n = len(nums)
DP = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
DP[i][i] = nums[i]
for k in range(n-1, 0, -1):
for i in range(k):
j = i + n - k
DP[i][j] = max(nums[i] - DP[i+1][j], nums[j] - DP[i][j-1])
return DP[0][n-1] >= 0
```
Sign in with Wallet
Connect another wallet