## 1025. Divisor game

**Game theory cơ bản**:

- Trạng thái tầm thường: không thể đi thêm một nước nào nữa -> chắc chắn thua.
- Nếu một trạng thái nào đó đẩy được đối thủ về trạng thái tầm thường -> chắc chắn thắng.
- Nếu một trạng thái nào đó chỉ có thể đẩy đối phương vào trạng thái chắc chắn thắng -> chắc chắn thua.
- Nếu một trạng thái nào đó đẩy được đối thủ vào một trạng thái thua -> chắc chắn thắng.

Từ trạng thái phức tạp hơn -> trạng thái đơn giản. -> DP.

## 72. Edit distance

-> đọc lại LCS (Longest common subsequence).

## 494. Target Sum

Có 2 cách giải:

1. Backtrack $O(2 ^ n)$ (do $n \le 20$)
-> Lưu ý: để backtrack khéo, ta nên lưu thêm 1 params vào hàm backtrack:

`backtrack(int x, int sum)` -> khi đó, ta không cần phải duyệt +- lại từ đầu sau khi sinh được xong một config nữa, mà tính luôn.

3. DP

$f(i, j)$ = có bao nhiêu cách để tạo ra các biểu thức sử dụng $A[1..i]$, sao cho tổng bằng đúng $j$.

$0 \le i \le 20$
$-20000 \le j \le 20000$

-> để lưu kết quả DP, các bạn sẽ phải sử dụng 1 trong 2 kỹ thuật:

- Dùng map, hoặc unordered_map để lưu trữ các phần tử index âm.
- Transpose $j' = j + 20001$ để sử dụng các index dương trong array.

Sau đó, viết công thức DP như bình thường.

## 741. Cherry Pickup

Code mẫu (low_): https://leetcode.com/problems/cherry-pickup/submissions/1281386537

Đầu tiên, các bạn hãy thử giải với trường hợp đi 1 chiều?

$dp(i, j) = -inf$ (nếu $a[i][j] == -1$, hoặc $i < 0, j < 0$)
$dp(i, j) = max(dp(i - 1, j), dp(i, j - 1)) + a[i][j]$

Để chọn ra cùng lúc 2 đường, mà tổng hai đường có số cherry nhặt được tối ưu nhất, ta cần lưu cả 2 tọa độ hiện thời: $(i, j)$ và $(u, v)$:

$dp(i, j, u, v)$ = max(dp(i - 1, j, u - 1, v), dp(i - 1, j, u, v - 1), ...) + ...$

$1 \le i, j, u, v \le n \le 50$

-> hoàn toàn $O(n ^4)$ có thể chạy được.

$i + j == u + v$

-> Có thể cải tiến rằng chỉ lưu $dp(i, j, u)$, khi đó, có thể tính $v = i + j - u$ và tiếp tục chuyển trạng thái.

-> cải tiến được bộ nhớ xuống $O(n^3)$.

## 32. Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/submissions/1284748445/

Luồng suy nghĩ WA và cải tiến bằng DP được comment ở trong đoạn code trên.

Lưu ý: kỹ thuật tìm vị trí ngoặc mở tương ứng với từng ngoặc đóng sử dụng stack.

## 174. Dungeon Game

Quan sát: nếu một ngưỡng máu $x$ nào đó mà có thể thỏa mãn nhân vật có thể đi đến cuối mà vẫn sống, thì với mọi ngưỡng máu $y >= x$ -> nhân vật cũng sẽ sống.

-> Binary search để tính ra ngưỡng máu.

Câu hỏi: với một ngưỡng máu $x$ nhất định nào đó, thì ta tính ra xem nhân vật có thể đi đến cuối ngục được không?

$dp(i, j)$ ngưỡng máu tối đa mà nhân vật có thể dư lại khi đi đến ô $(i, j)$. -> Nếu ngưỡng máu tối đa mà = 0 hoặc âm, thì $dp(i, j) = -inf$

## 42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/submissions/1283621119/?envType=problem-list-v2&envId=mlayhpdh