Quy hoạch động chữ số là sao? Hãy cho 1 ví dụ bài tập cụ thể
Quy hoạch động chữ số (hoặc quy hoạch động cho bài toán số) là một kỹ thuật trong lập trình và tối ưu hóa, dùng để giải quyết các bài toán có cấu trúc tối ưu con. Nói chung, quy hoạch động áp dụng cho các bài toán mà có thể được chia thành các bài con và kết quả của bài toán lớn hơn có thể được xác định từ kết quả của các bài toán con.
**Ví dụ bài tập quy hoạch động với chữ số:**
Giả sử bạn có một chuỗi số và bạn muốn xác định cách đếm số cách có thể phân tách chuỗi đó thành các số khác nhau sao cho mỗi số không quá 9 (tức là từ 1 đến 9).
### Bài toán:
Cho phép người dùng nhập vào một chuỗi số, ví dụ "123", và yêu cầu tìm số cách phân tách chuỗi này thành các số hợp lệ.
**Ví dụ:**
Chuỗi "123" có thể phân tách thành các số như sau:
1. 1 | 2 | 3
2. 12 | 3
3. 1 | 23
4. 123
### Giải pháp sử dụng quy hoạch động:
1. **Xác định trạng thái:** Gọi `dp[i]` là số cách phân tách chuỗi con từ chỉ số 0 đến `i`.
2. **Khởi tạo các giá trị:**
- `dp[0] = 1`: Một cách để không phân tách (chuỗi rỗng).
- `dp[1] = 1`: Chỉ có 1 chữ số, không có cách phân tách nào khác.
3. **Chuyển đổi trạng thái:** Duyệt qua từng chỉ số từ 2 đến độ dài của chuỗi:
- Nếu chữ số tại `i-1` không phải là '0', thì `dp[i] += dp[i-1]`.
- Nếu hai chữ số tại `i-2` và `i-1` hợp lệ (tức là từ 10 đến 26), thì `dp[i] += dp[i-2]`.
4. **Kết quả:** Giá trị tại `dp[n]` (n là chiều dài chuỗi) sẽ cho biết số cách phân tách chuỗi.
### Cài đặt bằng Python:
```python
def count_decodings(s):
if not s:
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # Chuỗi rỗng
dp[1] = 1 if s[0] != '0' else 0 # Phân tách một chữ số
for i in range(2, n + 1):
# Một chữ số
if s[i-1] != '0':
dp[i] += dp[i-1]
# Hai chữ số
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
# Test với chuỗi "123"
s = "123"
print(count_decodings(s)) # Kết quả: 3
```
### Kết quả:
Khi chạy chương trình với chuỗi "123", hồi đáp sẽ cho biết có 3 cách phân tách valid.
Hy vọng rằng giải thích và ví dụ trên giúp bạn hiểu rõ về quy hoạch động và ứng dụng của nó trong bài toán chữ số!