# PyZ - basic DP

## QHĐ là gì?
- Đặt một mảng gì đó ($F$), cần đi tính
- Tìm một công thức để tính (thường là tính cái sau dựa vào cái trước đó)

Ví dụ đơn giản nhất là prefix-sum: `S[i] = S[i-1] + a[i]`

## Bài 1:
Các bước
- Tính $a$
- Tính `F[i] = max(F[i-1], a[i])` để trả lời các câu hỏi tìm max được nhanh

## Bài 2:
(giải thích công thức)

"một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con"

Giả sử tại tháng hiện tại, có
- $x$ đôi thỏ 1 tháng tuổi
- $y$ đôi thỏ $\ge$ 2 tháng tuổi

$\Rightarrow$ Qua tháng sau, số lượng thỏ là:
- $y$ đôi thỏ 1 tháng tuổi (mới được đẻ thêm)
- $x+y$ đôi thỏ $\ge$ 2 tháng tuổi ($y$ đôi cũ + $x$ đôi mới lớn lên)

$(x,y)$ qua các tháng: $(0,1), (1,1), (1,2), (2,3), (3,5), (5,8), ...$

## Bài 4:
Cách làm tham lam sẽ bị sai test sau:

4
2 3 0 0

Hướng giải: QHĐ. Đặt `f[i]` là chi phí ít nhất để con ếch nhảy được từ $1$ tới $i$. Tính `f[i]` từ `f[i-1]` và `f[i-2]` (từ vị trí đó, nhảy thêm 1 lần tới vị trí $i$)

## Bài 3:

### Ví dụ
Tạo tổng 1: $1$
Tạo tổng 2: $1 \, 1, 2$
Tạo tổng 3:
+ có cách nào tạo được $1$?
- $1$
- thêm $2$ vào sẽ tạo được $3$
$\Rightarrow 1 \, 2$
+ có cách nào tạo được $2$?
- $1\,1 , 2$
- thêm $1$ vào sẽ tạo được $3$
$\Rightarrow 1\,1\,1 , 2\,1$
+ chỉ có số $3$
Số lượng cách là: $1 + 2 + 1 = 4$

Tạo tổng 4:
+ có cách nào tạo được $1$?
- $1$
- thêm $3$ vào sẽ tạo được $4$
$\Rightarrow 1 \, 3$
+ có cách nào tạo được $2$?
- $1\,1, 2$
- thêm $2$ vào sẽ tạo được $4$
$\Rightarrow 1\,1\,2,2\,2$
+ có cách nào tạo được $3$?
- $1\,2,1\,1\,1,\,2\,1,3$
- thêm $1$ vào sẽ tạo được $4$
$\Rightarrow 1\,1\,2, 1\,1\,1\,1,\, 2\,1\,1, 3\,1$
+ có cách nào tạo được 0?
- (không có số nào)
- thêm 4 vào
- $\Rightarrow 4$

Vậy số lượng cách $= 1 + 2 + 4 + 1$
Hay
$f[4] = f[1] + f[2] + f[3] + f[0]$

### Sol

Từ ý tưởng bài trên, ta áp dụng cho bài này.

Đặt `f[i]` là số cách tạo nên tổng $i$. Giả sử lần cuối cùng ta gieo xúc xắc ra được $j$.

Vậy tổng trước đó phải là $i-j$. Có bao nhiêu cách tạo ra được tổng $i-j$ thì sẽ có thêm bấy nhiêu cách để tạo tổng $i$. ($j$ chạy từ $1 \rightarrow 6$)

Do đó `f[i] += f[i-j]`

## Bài 5:
Tham lam hoặc QHĐ đều được